Cod sursa(job #580024)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 12 aprilie 2011 17:45:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstdio>
#include<vector>
#include<queue>
#define Nmax 50001
using namespace std;

int N,M,t[Nmax];

vector <int> a[Nmax];
queue  <int> q,sol;

int main(){
	
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=M;++i){
		
		int x,y;
		scanf("%d%d",&x,&y);
		
		a[x].push_back(y);
		t[y]++;
	}
	
	for(int i=1;i<=N;++i)
		if(t[i]==0)
			q.push(i);
		
	while(!q.empty()){
		
		int nod=q.front();
		q.pop();
		sol.push(nod);
		
		for(vector<int>::iterator it=a[nod].begin();it!=a[nod].end();++it){
			t[*it]--;
			if(t[*it]==0)
				q.push(*it);}
	}
	
	while(!sol.empty()){
		printf("%d ",sol.front());
		sol.pop();
	}
return 0;
}