Cod sursa(job #631692)

Utilizator Balmus_MaximBalmus Maximilian Balmus_Maxim Data 9 noiembrie 2011 16:50:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <vector>
using namespace std;

int n,m;
vector <int> g[100010];
int v[100010],vv[100010],z[100010];
int i,a,b;
int in=1,sf=0;

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sorteret.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		v[b]++;
	}
	for(i=1;i<=n;i++){
		if(v[i]==0){
			sf++;
			vv[sf]=i;
			z[i]=1;
			printf("%d ",i);
		}
	}
	
	while(in<=sf){
		for(i=0;i<g[vv[in]].size();i++){
			if(z[g[vv[in]][i]]!=1){
				if(v[g[vv[in]][i]]-1==0){
					printf("%d ",g[vv[in]][i]);
					vv[++sf]=g[vv[in]][i];
					z[g[vv[in]][i]]=1;
					v[g[vv[in]][i]]--;
				}else{
					v[g[vv[in]][i]]--;
				}
			}
		}
		in++;
	}
	return 0;
}