Cod sursa(job #944672)

Utilizator alecsandrualex cuturela alecsandru Data 29 aprilie 2013 12:47:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,a,b,i;
vector <int> succ[51000];
queue <int> q;
int pred[51000];
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        pred[b]++;
        succ[a].push_back(b);
    }
    for(i=1;i<=n;i++)
    {
        if(!pred[i])
            q.push(i);
    }
    while(!q.empty())
    {
        a=q.front();
        printf("%d ",a);
        for(i=0;i<succ[a].size();i++)
        {
            pred[succ[a][i]]--;
            if(!pred[succ[a][i]])
                q.push(succ[a][i]);
        }
        q.pop();
    }
    return 0;
}