Cod sursa(job #2032828)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 5 octombrie 2017 19:08:19
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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)
    {
        ok[0]=0;
        scanf("%d %d",&tmp1,&tmp2);
        for(int i=0;i<v[tmp1].size();++i)
            if(v[tmp1][i]==tmp2)
                ok[0]=1;
        if(ok[0]==0)
        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[q[st]]==1)
        {
            for(int i=0;i<v[q[st]].size();++i){
                q[++dr]=v[q[st]][i];
                ok[q[dr]]=1;
            }
            ok[q[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;
}