Cod sursa(job #1794784)

Utilizator FlowstaticBejan Irina Flowstatic Data 1 noiembrie 2016 18:44:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#include <queue>

#define pb push_back
#define NMAX 50100
#define FOR(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

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

vector<int> g[NMAX];
int dg[NMAX];
int N,M;
queue<int> Q;

int main()
{
    fin>>N>>M;
    int a,b;
    FOR(i,1,M)
        fin>>a>>b,g[a].pb(b),dg[b]++;

    FOR(x,1,N)
        if(dg[x] == 0) Q.push(x);

    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        fout<<x<<" ";
        for(int i = 0; i<g[x].size(); i++)
        {
            dg[g[x][i]]--;
            if(dg[g[x][i]] == 0) Q.push(g[x][i]);
        }
    }
    fout<<'\n';
    return 0;
}