Cod sursa(job #145450)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 28 februarie 2008 20:31:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

#define MAXN 50005

int N;
vector<int> con[MAXN];
stack<int> st;

vector<bool> used;

inline void dfs( int k )
{
	if (used[k])
		return;
	used[k] = 1;

	vector<int> :: iterator it;
	for (it = con[k].begin(); it != con[k].end(); it++)
		dfs(*it);
	st.push(k);
}

int main()
{
	freopen("sortaret.in", "rt", stdin);
	freopen("sortaret.out", "wt", stdout);

	int M;
	scanf("%d %d", &N, &M);
	for (; M; M--)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		x--; y--;

		con[x].push_back(y);
	}

	used.resize(N);
	for (int i = 0; i < N; i++)
		dfs(i);
	
	for (; !st.empty(); st.pop())
		printf("%d ", st.top() + 1);
	printf("\n");

	return 0;
}