Cod sursa(job #2032821)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 5 octombrie 2017 18:51:27
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>

using namespace std;

int q[100005];
int ok[50005];
int sol[50005];

vector <int> v[50005];

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int st=0,dr=0,n,m,tmp1,tmp2;

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&tmp1,&tmp2);
        v[tmp1].push_back(tmp2);
        ok[tmp2]=1;
    }

    for(int i=1;i<=n;++i)
    {
        if(ok[i]==0)
            q[++dr]=i;
        ok[i]=1;
    }

    while(st<=dr)
    {
        ++st;
        if(ok[st]==1)
        {
            for(int i=0;i<v[q[st]].size();++i)
                q[++dr]=v[q[st]][i];
            ok[st]=0;
        }
    }

    int nr=0;
    for(int i=dr;i>0;--i)
    {
        if(ok[q[i]]==0)
            sol[++nr]=q[i];
        ok[q[i]]=1;
    }

    for(int i=nr;i>0;--i)
        printf("%d ",sol[i]);

    return 0;
}