Havel Hakimi UVA-12786 Friendship Networks, C++ (gcc)

Havel Hakimi UVA-12786 Friendship Networks

// HARE KRISNA

#include <bits/stdc++.h>

using namespace std;

int n;
vector <int> degree;

bool HAVEL_HAKIMI()
{
    sort(degree.begin(), degree.end(), greater <int>() );
    
    int num = degree[0];
    
    degree.erase(degree.begin());
    
    bool zero = true;
    
    assert(num <= degree.size());
    
    for (int i = 0; i < num; i++)
    {
        degree[i] -= 1;
        
        if (degree[i])
        {
            zero = false;
        }
        
        if (degree[i] < 0)
        {
            return false;
        }
    }
    if (zero || degree.empty())
    {
        return true;
    }
    
    return HAVEL_HAKIMI();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    while (cin >> n)
    {
        int odd = 0;
        bool ok = true;
        
        degree.clear();
        
        for (int i = 0; i < n; i++)
        {
            int num;
            cin >> num;
            
            if (num >= n)
            {
                ok = false;
            }
            
            if (num & 1)
            {
                odd++;
            }
            
            degree.push_back(num);
        }
        
        if ((odd & 1) || !ok)
        {
            cout << "0" << endl;
            
            continue;
        }
        
        if (HAVEL_HAKIMI())
        {
            cout << "1" << endl;
        }
        
        else
        {
            cout << "0" << endl;
        }
    }
}


run \| edit \| history \| help	0