Cod sursa(job #2668202)

Utilizator BulaceanuAlexandraBulaceanu Alexandra-Irina BulaceanuAlexandra Data 4 noiembrie 2020 17:17:07
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> muchii[100010];
map<int, bool> vizitat;
vector<int> grad;
vector<int> sol;

void dfs(int nodCurent) {
	vizitat[nodCurent] = true;
	for (int vecin : muchii[nodCurent]) {
		if (!vizitat[vecin]) {
			grad[vecin]--;
			if (grad[vecin] == 0) sol.push_back(vecin);
			dfs(vecin);
		}
	}
}

int main() {
	int nrCompConexe = 0;
	int n, m, x, y;
	fin >> n >> m;

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

	for (int i = 1;i <= n;i++) {
		if (grad[i] == 0) sol.push_back(i);
	}

	dfs(sol[1]);
	//reverse(sol.begin(),sol.end());

	for (int elem : sol)
	{
		fout << elem << " ";
	}
}