Cod sursa(job #392275)

Utilizator hulparuadrianhulparu adrian hulparuadrian Data 7 februarie 2010 07:43:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>
#include<vector>
using namespace std;

#define SIZE 50010
int N, M, c[SIZE], solutie[SIZE], n;
vector <int> graf[SIZE];

void DFS(int u)
{
	c[u] = 1;
	for(int j = 0; j < graf[u].size(); j++)
		if(!c[graf[u][j]]) DFS(graf[u][j]);
	solutie[++n] = u;
}

int main()
{
	int i, x, y;
	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);
		graf[x].push_back(y);
	}
	fclose(stdin);
	
	for(i = 1; i <= N; i++)
		if(!c[i]) DFS(i);
	
	for(i = n; i >= 1; i--)
		printf("%d ", solutie[i]);
		
	fclose(stdout);
	return 0;
}