Cod sursa(job #373046)

Utilizator iulia609fara nume iulia609 Data 12 decembrie 2009 15:12:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
#include<vector>
#define MAXN 50005
using namespace std;

int N, M, U[MAXN], R[MAXN], W[MAXN], x, y, k; 

vector<int> V[MAXN];

void solve(int nod)
{
	if(U[nod]) return;
	
	U[nod] = 1;
	int sf = V[nod].size();
	for(int i = 0; i < sf; i++)
	{
		if(U[V[nod][i]] == 0)
			solve(V[nod][i]);
	}
	R[++k] = nod;
	//printf("%d ", nod);
}

int main()
{ int i;
	
	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);
		V[y].push_back(x);
		W[x]++;
	}
	
	for(i = 1; i <= N; i++)
		if(W[i] == 0)
			solve(i);
		
	for(i = 1; i <= N; i++)
		printf("%d ", R[i]);
	
	printf("\n");
	
	return 0;
}