Cod sursa(job #2172606)

Utilizator infomaxInfomax infomax Data 15 martie 2018 17:07:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream F("sortaret.in");
ofstream G("sortaret.out");

int n, m, x, y, deg[50005];
queue<int> q, sol;
vector<int>a[50005];

int main()
{
    F>>n >> m;
    for(int i = 1; i <= m; ++ i){
        F >>x>> y;
        a[x].push_back(y);
        deg[y]++;
    }
    for(int i = 1; i <= n; ++ i)
        if(!deg[i]) q.push(i);
    while(!q.empty()){
        x=q.front();
        q.pop();
        sol.push(x);
        for(auto it:a[x]){
            deg[it]--;
            if(!deg[it])q.push(it);
        }
    }
    while(!sol.empty()){
        G << sol.front()<< " ";
        sol.pop();
    }
    return 0;
}