Cod sursa(job #2528508)

Utilizator enedumitruene dumitru enedumitru Data 21 ianuarie 2020 23:38:21
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define Nmax 50100
using namespace std;
ifstream f("sortaret.in"); ofstream g("sortaret.out");
int n,m,gri[Nmax],Q[Nmax];
vector<int> G[Nmax];
/// deg[x] = gradul interior al nodului x
/// folosesc o coada Q in care introduc pe rand nodurile care au gradul interior zero
/// complexitate O(N+M)
int main(void)
{   f>>n>>m;
    for(int a,b,i=1;i<=m;i++) {f>>a>>b; G[a].push_back(b); gri[b]++;};
    for(int i=1;i<=n;i++)
        if(gri[i]==0) Q[++Q[0]]=i;
    for(int x,i=1;i<=n;i++)
    {   x=Q[i];
        vector <int> :: iterator it=G[x].begin(),sf=G[x].end();
        for(;it!=sf;++it)
        {   gri[*it]--;
            if(gri[*it]==0) Q[++Q[0]]=*it;
        }
    }
    for(int i=1;i<=n;i++) g<<Q[i]<<' ';
    g.close(); f.close(); return 0;
}