Cod sursa(job #2231734)

Utilizator gabrielxCojocaru Gabriel-Codrin gabrielx Data 15 august 2018 19:12:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int N, M;
vector<bool> viz(50001);
vector<vector<int>> adj(50001);
vector<int> topsort;

void dfs(int node) {
	viz[node] = true;

	for (int i = 0; i < adj[node].size(); ++i) {
		if (viz[adj[node][i]] == false) {
			dfs(adj[node][i]);
		}
	}

	topsort.push_back(node);
}

int main() {
	int x, y;

	fin >> N >> M;

	for (int i = 1; i <= N; ++i) {
		viz[i] = false;
		adj[i].clear();
	}

	for (int i = 1; i <= M; ++i) {
		fin >> x >> y;
		adj[x].push_back(y);
	}

	for (int i = 1; i <= N; ++i) {
		if (viz[i] == false) {
			dfs(i);
		}
	}

	for (int i = N - 1; i >= 0; --i) {
		fout << topsort[i] << ' ';
	}
}