Find if a degree sequence can form a simple graph | Havel | C ++ implementation of the approach ; Function that returns true if a simple graph exists ; Keep performing the operations until one of the stopping condition is met ; Sort the list in non - decreasing order ; Check if all the elements are equal to 0 ; Store the first element in a variable and delete it from the list ; Check if enough elements are present in the list ; Subtract first element from next v elements ; Check if negative element is encountered after subtraction ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool graphExists ( vector < int > & a , int n ) { while ( 1 ) { sort ( a . begin ( ) , a . end ( ) , greater < > ( ) ) ; if ( a [ 0 ] == 0 ) return true ; int v = a [ 0 ] ; a . erase ( a . begin ( ) + 0 ) ; if ( v > a . size ( ) ) return false ; for ( int i = 0 ; i < v ; i ++ ) { a [ i ] -- ; if ( a [ i ] < 0 ) return false ; } } } int main ( ) { vector < int > a = { 3 , 3 , 3 , 3 } ; int n = a . size ( ) ; graphExists ( a , n ) ? cout << " Yes " : cout << " NO " << endl ; return 0 ; }