Cod sursa(job #3320832)

Utilizator _irina__irina tanase _irina__ Data 7 noiembrie 2025 15:07:02
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <bits/stdc++.h>
using namespace std;

void graphic_sequence()
{
    int nr_seq, nr_nodes;
    
    cin >> nr_seq;

    for(int i = 0; i < nr_seq; i ++)
    {
        cin >> nr_nodes;
        vector <int> L(nr_nodes + 1, 0);
        int nr_odd = 0;

        for(int j = 0; j < nr_nodes; j ++)
        {
            int node; 
            cin >> node;
            if(node % 2) nr_odd ++;
            L.push_back(node);
        }

        if(nr_odd % 2) 
            cout << "IMPOSSIBLE\n";
        else
        {
            sort(L.begin(), L.end());

            for(int d1 = 0; d1 < nr_nodes; d1 ++)
            {
                for(int d2 = d1 + 1; d2 < nr_nodes && L[d1] > 0; d2 ++)
                {
                    L[d1] --;
                    L[d2] --;
                }
            }

            bool pos = true;

            for(int d1 = 0; d1 < nr_nodes; d1++)
                if(L[d1]) pos = false;

            if(!pos)
                cout << "IMPOSSIBLE\n";
            else cout << "POSSIBLE\n";
        }
    }
}

void tree_construction()
{

    int deg_sum = 0, nodes;

    cin >> nodes;

    vector<pair<int, int>> degrees;

    for(int i = 1; i <= nodes; i ++)
    {
        int deg; 
        cin >> deg;
        deg_sum += deg;
        degrees.push_back({deg, i});
    }       

    if(deg_sum != 2 * (nodes - 1))
        {cout << -1; return;}

    sort(degrees.begin(), degrees.end(), [] (const pair<int, int>& a, const pair<int, int>& b) {
	return a.first > b.first;
	});

    vector<pair<int, int>> vertices;

    for(int i = 0; i < nodes; i ++)
    {
        for(int j = i + 1; j < nodes && degrees[i].first > 0; j ++)
        {
            if(degrees[j].first > 0)
            {
                degrees[i].first --;
                degrees[j].first --;
                vertices.push_back({degrees[i].second, degrees[j].second});
            }
        }
    }

    bool pos = true;

    for(int i = 0; i < nodes; i ++)
        if(degrees[i].first){ pos = false;}

    if(pos == false) {cout << -1; return;}

    for(auto v: vertices)
        cout << v.first << ' ' << v.second << '\n';

}

int main()
{
    tree_construction();
    return 0;
}