Cod sursa(job #2987041)

Utilizator Radu_TudorRadu Tudor Radu_Tudor Data 1 martie 2023 21:12:53
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const string FILE_NAME = "sortaret";
const int N_MAX = 5e4 + 1;

ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");

int N, M;
vector<int> edges[N_MAX];

// dfs-related
queue<int> Q;
bool visited[N_MAX];

// result
vector<int> list;

void read() {

	fin >> N >> M;

	int from, to;
	for (int i = 1; i <= M; i++) {

		fin >> from >> to;

		edges[from].push_back(to);
	}
}

void dfs(int node) {

	visited[node] = true;

	for (size_t i = 0; i < edges[node].size(); i++)
		if (visited[edges[node][i]] == false)
			dfs(edges[node][i]);

	list.push_back(node);
}

void solve() {

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

	reverse(list.begin(), list.end());
}

void display() {

	for (auto it : list)
		fout << it << " ";
}

int main() {

	read();
	solve();
	display();

	fin.close();
	fout.close();

	return 0;
}