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