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