Cod sursa(job #2790693)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 29 octombrie 2021 12:59:44
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;
vector <int> v[50001];
queue <int> q;
int deg[50000];
int main()
{
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

    int n, m;
    cin >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        deg[b] ++;
    }
    for ( int i = 1; i <= n; i ++)
    {
        if(deg[i] == 0)
        {
            q.push(i);
        }
    }
    for ( int i = 1; i <= n; i++)
    {
        if(deg[i] == 0)
        {
            for(auto x: v[i])
            {
                deg[x]--;
                if(deg[x] == 0)
                {
                    q.push(x);
                }
            }
        }
    }
    for ( int x = q.front() ; x<=q.back();x ++)
    {
        cout << x << " ";
    }
    return 0;
}