Cod sursa(job #1705068)

Utilizator kittDenisa kitt Data 19 mai 2016 21:15:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <stack>
#include <vector>

#define NMAX 50001

using namespace std;

vector<int> adjList[NMAX];
int visited[NMAX];
vector<int> sol;
int n, m, s;

void DFS(int root) {
	if (visited[root] == 1) {
	if (visited[root] == 0) {
		visited[root] = 1;
		for (int i = 0; i < adjList[root].size(); ++i) {
			DFS(adjList[root][i]);
		}
		visited[root] = 2;
		sol.push_back(root);
	}
}

int main() {
	FILE *in, *out;
	in = fopen("sortaret.in", "r");
	out = fopen("sortaret.out", "w");
	int a, b;
	fscanf(in, "%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%d%d", &a, &b);
		adjList[a].push_back(b);
	}

	for (int i = 1; i <= n; ++i) {
		if (visited[i] == 0) {
			DFS(i);
		}
	}
	for (int i = sol.size() - 1; i >= 0; --i) {
		fprintf(out, "%d ", sol[i]);
	}
}