Cod sursa(job #2791283)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 30 octombrie 2021 12:26:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>

struct node {
	bool viz = false;
	bool root = true;
	std::vector <int> con;
};

node web[50005];

void dfs(int pos) {
	static std::ofstream fout("sortaret.out");
	web[pos].viz = true;
	for (int chd : web[pos].con) {
		if (!web[chd].viz) {
			dfs(chd);
		}
	}
	fout << pos + 1 << ' ';
}

int main() {
	std::ifstream fin("sortaret.in");
	int nrn, nrm, pos1, pos2;
	fin >> nrn >> nrm;
	for (int index = 0; index < nrm; index++) {
		fin >> pos1 >> pos2;
		pos1--;
		pos2--;
		web[pos2].con.push_back(pos1);
		web[pos1].root = false;
	}
	for (int index = 0; index < nrn; index++) {
		if (web[index].root && !web[index].viz) {
			dfs(index);
		}
	}
}