Cod sursa(job #2202844)

Utilizator roberttrutaTruta Robert roberttruta Data 10 mai 2018 08:57:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[50002];
int n,m,i,a,b,p,t,grad[50002],c[50002];
bool viz[50002];
int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        grad[b]++;
    }

    for(i=1;i<=n;i++)
        if(grad[i]==0)
    {
        c[++t]=i;
        viz[i]=1;
    }
    p=1;
    while(p<=t)
    {
        for(i=0;i<v[c[p]].size();i++)
            if(viz[v[c[p]][i]]==0)
        {
            grad[v[c[p]][i]]--;
            if(grad[v[c[p]][i]]<=0)
            {
                viz[v[c[p]][i]]=1;
                c[++t]=v[c[p]][i];
            }
        }
        p++;
    }
    for(i=1;i<=t;i++)
        g<<c[i]<<' ';
    return 0;
}