Cod sursa(job #962979)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 16 iunie 2013 11:35:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int x,n,m,i,x1,y1,cnt[50009];

queue <int> Q;
vector <int> v[50009];
vector <int> :: iterator it;

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d",&n);
    scanf("%d",&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d",&x1);
        scanf("%d",&y1);
        v[x1].push_back(y1);
        ++ cnt[y1];
    }
    for(i = 1; i <= n; ++ i)
        if(cnt[i] == 0)
        {
            Q.push(i);
            printf("%d ",i);
        }
    for(x = Q.front(); !Q.empty() ; Q.pop(), x = Q.front() )
        for(it = v[x].begin(); it != v[x].end(); ++ it)
        {
            -- cnt[*it];
            if(cnt[*it] == 0)
            {
                Q.push( *it );
                printf("%d ", *it );
            }
        }
    return 0;
}