Check whether given degrees of vertices represent a Graph or Tree | C ++ program to check whether input degree sequence is graph or tree ; Function returns true for tree false for graph ; Find sum of all degrees ; Graph is tree if sum is equal to 2 ( n - 1 ) ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( int degree [ ] , int n ) { int deg_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) deg_sum += degree [ i ] ; return ( 2 * ( n - 1 ) == deg_sum ) ; } int main ( ) { int n = 5 ; int degree [ ] = { 2 , 3 , 1 , 1 , 1 } ; if ( check ( degree , n ) ) cout << " Tree " ; else cout << " Graph " ; return 0 ; }