Cod sursa(job #2129997)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 13 februarie 2018 12:52:15
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#define pb push_back

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m, nr, gi[50005];
vector<int> niv, L[50005];

int main()
{
    int i, j, x, y, ok;

    fin >> n >> m;
    for (i=1;i<=n;i++)
    {
        ok = 1;
        fin >> x >> y;
        for (j=0;j<L[x].size()&&ok;j++)
            if (L[x][j] == y)
                ok = 0;
        if (ok)
        {
            L[x].pb(y);
            gi[y]++;
        }
    }
    while (nr < n)
    {
        niv.clear();
        for (i=1;i<=n;i++)
            if (!gi[i])
            {
                niv.pb(i);
                nr++;
                fout << i << ' ';
            }
        for (i=0;i<niv.size();i++)
        {
            gi[niv[i]]=-1;
            for (j=0;j<L[niv[i]].size();j++)
                gi[L[niv[i]][j]]--;
        }
    }
    return 0;
}