Cod sursa(job #650000)

Utilizator Marius96Marius Gavrilescu Marius96 Data 17 decembrie 2011 10:12:28
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

vector<int> v[50005];
int in[500005];
queue<int> q;
int main(){
	int x,y;
	freopen("sortaret.in","r",stdin);
	//freopen("sortaret.out","w",stdout);
	int n,m,mm;
	scanf("%d%d",&n,&m);
	mm=m;
	while(mm--){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		in[y]++;
	}
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(vector<int>::iterator it=v[x].begin();it!=v[x].end();it++){
			in[*it]--;
			if(!in[*it])q.push(*it);
		}
		printf("%d ",x);
	}
	return 0;
}