Cod sursa(job #2572337)

Utilizator deniros14Anicai Denis deniros14 Data 5 martie 2020 12:32:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int m, n, Q[50005], deg[50005];
vector <int> G[50005];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a, b;
        fin>>a>>b;
        G[a].push_back(b);
        deg[b]++;
    }

    for(int i=1;i<=n;i++)
    {
        if(deg[i] == 0) Q[++Q[0]] = i;
    }

    vector<int>::iterator it;
    for(int i=1;i<=n;i++)
    {
        int x = Q[i];
        for(it = G[x].begin(); it != G[x].end(); it++)
        {
            deg[*it]--;
            if(deg[*it] == 0) Q[++Q[0]] = *it;
        }
    }


    for(int i=1;i<=n;i++)
    {
        fout<<Q[i]<<' ';
    }
}