Cod sursa(job #664781)

Utilizator timeiutzaTimea Balan timeiutza Data 20 ianuarie 2012 19:56:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;

#define PB push_back
#define MKP make_pair
#define maxN 50005

deque <int> Q;
vector <int> lista[maxN];
int tata[maxN], viz[maxN];

void dfs (int nod)
{
	viz[nod] ++;
	
	for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		dfs (lista[nod][i]);
	
	if (viz[nod] == tata[nod] || !tata[nod]) Q.PB (nod);
}

int main()
{
	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int x, y;
		
		scanf ("%d %d", &x, &y);
		
		lista[x]. PB (y);
		
		tata[y] = true;
	}
	
	for (int i = 1; i <= N; ++ i)
	{
		if (tata[i]) continue;
		
		dfs (i);
	}
	
	for (int i = Q.size() - 1; i >= 0; -- i)
	{
		printf ("%d ", Q[i]);
	}
	
	return 0;
}