Cod sursa(job #2073746)

Utilizator frumcrsFrum Cristian-Mihai frumcrs Data 23 noiembrie 2017 17:27:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 50001

vector<int> a[NMAX];
queue<int> Q;
vector<int> solutie;
int grad_interior[NMAX];

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

int main()
{
    int n,m,i,x,y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        grad_interior[y]++;
    }
    for(i=1;i<=n;i++)
    {
        if(grad_interior[i]==0)
        {
            Q.push(i);
        }
    }
    while(Q.empty()==0)
    {
        int nod=Q.front();
        fout<<nod<<" ";
        Q.pop_front();
        for(auto x:a[nod])
        {
            grad_interior[x]--;
            if(grad_interior[x]==0)
            {
                Q.push_back(x);
            }
        }

    }
}