Find if a degree sequence can form a simple graph | Havel | Java 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
import java . util . * ; @ SuppressWarnings ( " unchecked " ) class GFG { static boolean graphExists ( ArrayList a , int n ) { while ( true ) { Collections . sort ( a , Collections . reverseOrder ( ) ) ; if ( ( int ) a . get ( 0 ) == 0 ) return true ; int v = ( int ) a . get ( 0 ) ; a . remove ( a . get ( 0 ) ) ; if ( v > a . size ( ) ) return false ; for ( int i = 0 ; i < v ; i ++ ) { a . set ( i , ( int ) a . get ( i ) - 1 ) ; if ( ( int ) a . get ( i ) < 0 ) return false ; } } } public static void main ( String [ ] args ) { ArrayList a = new ArrayList ( ) ; a . add ( 3 ) ; a . add ( 3 ) ; a . add ( 3 ) ; a . add ( 3 ) ; int n = a . size ( ) ; if ( graphExists ( a , n ) ) { System . out . print ( " Yes " ) ; } else { System . out . print ( " NO " ) ; } } }