Cod sursa(job #1455413)

Utilizator Player1Player 1 Player1 Data 27 iunie 2015 22:52:44
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <vector>
#include <stack>

#define NMAX 50001

using namespace std;

vector <int> V[NMAX];
int N, M, i, j;
stack <int> S;
bool visited[NMAX] = {0};
int count =1;

void DFS(int index){
	//if(count == N)
	//	printf("%d", index);
	//else
	//	printf("%d ", index);
	count++;
	visited[index] = 1;
	for (j=0; j<V[index].size(); j++)
		if (visited[V[index][j]] == 0)
			DFS(V[index][j]);

	S.push(index);

}

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

	int x, y;

	scanf("%d %d ", &N, &M);

	for (i=0; i<M; i++){
		scanf("%d %d ", &x, &y);
		V[x].push_back(y);
	}

	//for (i=1; i<=N; i++){
	//	for (j=0; j<V[i].size(); j++)
	//		printf("%d ", V[i][j]);
	//	printf("\n");
	//}

	for(i=1; i<=N; i++){
		if(visited[i] == 0)
			DFS(i);
	}

	while(!S.empty()){
		printf("%d ", S.top());
		S.pop();
	}

	return 0;
}