4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Check the given list can be a degree list of some graph
4fd800b3a8 2011-02-23        kinaba: //   O(n^2)  (I suspect it can be made faster, though...)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM 398 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: //((
4fd800b3a8 2011-02-23        kinaba: // Havel-Hakimi
4fd800b3a8 2011-02-23        kinaba: //   If G[0], ..., G[n] (decreasing) is graphical,
4fd800b3a8 2011-02-23        kinaba: //   then G[1]-1, G[2]-1, ..., G[G[0]]-1, G[G[0]+1], .., G[n]
4fd800b3a8 2011-02-23        kinaba: //   is also graphical.
4fd800b3a8 2011-02-23        kinaba: //))
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: bool isGraphical( vector<int> G )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	sort( G.begin(), G.end() );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int>::iterator b = lower_bound( G.begin(), G.end(), 1 );
4fd800b3a8 2011-02-23        kinaba: 	vector<int>::iterator e = G.end();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	while( b < e )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int n = *(--e);
4fd800b3a8 2011-02-23        kinaba: 		if( e-b < n )
4fd800b3a8 2011-02-23        kinaba: 			return false;
4fd800b3a8 2011-02-23        kinaba: 		for(vector<int>::iterator i=e-n; i!=e; ++i)
4fd800b3a8 2011-02-23        kinaba: 			--*i;
4fd800b3a8 2011-02-23        kinaba: 		inplace_merge( b, e-n, e );
4fd800b3a8 2011-02-23        kinaba: 		b = lower_bound( G.begin(), G.end(), 1 );
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return true;
4fd800b3a8 2011-02-23        kinaba: }