Cod sursa(job #668412)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 24 ianuarie 2012 21:17:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 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;
}