UVa - 10720 Solution ( Graph Construction Solution )

=>Try Yourself First. For help Scroll Down .

Clearance : In this problem you have the value of N which is number of  NODES in a Graph and Number of Degrees ( Indegree & Outdegree ) for each NODES from 1 to N .  Supoose you have " 2 1 1 ". This means 2 nodes with 1 edge . Here you have to find whether you could Construct a Graph through the NODES and Degrees for each Node . There are some important Conditions to check whether the sequences of Degrees of N nodes  can Constuct a Graph. Those are :

i ) The sequence of Degrees must be sorted in Descending order ( Greater to Less ) and you can sort it by using STL sort() function in c++ snd qsort() in C. 

ii) The total Sum of Degrees must be Even ( Hand Shaking Theorem ).

iii ) Your Program must be iteratively obey this condition .   

 If anyone of those Conditions left behind then It will not be possible to Construct a Graph.. One Minor ( may be Major ) condition for which you may get Wrong Answer is to Check whether the First Element of the Sorted Series is not Greater than or Equal to N.

==> This Methode is Called Erdos - Gallai Theorem . You can also solve this problem by Havel - Hakimi Method . But I didn't try it .

Algorithm : 

1. Sort the list in Decreasing / Descending Order. 
2. Figure out the Total Sum of Degrees.
3. Check out whether it is Even or the First degree ( Sorted List ) is less than N . If not print " Not possible " . Then Continue.
4. If 3 is false then check apply this rule    and check out Constructing Graph is Possible or Not.

Code :


#include<bits/stdc++.h>

using  namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)==1 && n>0)
    {
        vector<int>seq;
        int x, sum = 0;
        for(int i=0; i<n; i++)
        {
            cin>>x;
            sum = sum + x;
            seq.push_back(x);
        }
        sort(seq.begin(),seq.end(), greater<int>());
        if(sum%2!=0 || seq[0]>=n)
        {
            printf("Not possible\n");
            continue;
        }

        bool flag = true;
        for(int k=0; k<n; k++)
        {
            int sumdi = 0;
            for(int i=0; i<k; i++)
                sumdi = sumdi + seq[i];
            int prok = k * (k-1);
            int summin = 0;
            for(int j=k; j<n; j++)
                summin = summin + min(seq[j],k);
            int tot = prok + summin;
            if(sumdi>tot)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            printf("Possible\n");
        else
            printf("Not possible\n");
    }
    return 0;
}


**** For Your Clearance , How can a Graph be Constructed through this sequence . Goven below . Let the input is "  10 3 3 3 3 3 3 3 3 3 3  "  .    The Graph is :   

       *---*---*

    / \  |  / \

    *---* | *---*

    \ /  |  \ /

    *---*---*

=>Question or Need Help ?? Leave a Comment .