Cod sursa(job #151309)

Utilizator alextheroTandrau Alexandru alexthero Data 7 martie 2008 23:30:36
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

#define nmax 50005

using namespace std;

int n, m, n1, n2;
char v[nmax];
vector <int> e[nmax], top;

void dfs(int x)
{
	v[x] = 1;
	for(int i = 0; i < (int)e[x].size(); i++)
		if(!v[e[x][i]]) dfs(e[x][i]);
	top.push_back(x);
}

int main()
{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d", &n1, &n2);
		e[n1].push_back(n2);
		e[n2].push_back(n1);
	}

	for(int i = 1; i <= n; i++)
		if(!v[i]) dfs(i);

	reverse(top.begin(), top.end());
	for(int i = 0; i < n; i++) printf("%d ", top[i]); printf("\n");
	return 0;
}