Cod sursa(job #606556)

Utilizator elfusFlorin Chirica elfus Data 4 august 2011 19:26:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 50100

using namespace std;

vector<int> L[NMAX];
int pred[NMAX];
queue<int> Q;

int main()
{
    int N,M,i,now,x,y;
    vector<int> :: iterator it;

    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
        {
            scanf("%d%d",&x,&y);
            L[x].push_back(y);
            pred[y] ++;
        }

    for(i=1;i<=N;i++)
        if(pred[i]==0)
            Q.push(i);

    while(!Q.empty())
    {
        now = Q.front();
        printf("%d ",now);
        for(it = L[now].begin() ; it != L[now].end(); it ++)
            {
                pred[*it]--;
                if(pred[*it] == 0)
                    Q.push(*it);
            }
        Q.pop();
    }

    return 0;
}