Cod sursa(job #3199412)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 1 februarie 2024 16:38:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("sortaret.in");
ofstream out("sortaret.out");
#define cin in
#define cout out
#endif // LOCAL

const int nmax = 5e4 + 7;
vector<int> g[nmax]; // graful nostru
vector<int> sortare; // vectorul in care vom retine sortarea topologica
int noduri_in[nmax]; // noduri_in[i] numara cate muchii avem de forma (x -> i)
// adica cate muchii intra in nodul i

void dfs(int node) {
	if(noduri_in[node] != 0) {
		// > 0 inseamna ca nu il putem scoate acum fiindca are parinti
		// -1 inseamna ca a fost vizitat deja

		return;
	}
	noduri_in[node] = -1; // il vizitam acum

	sortare.push_back(node); // il adaugam in sortare
	// si il stergem scotand -1 din fiecare nod vecin in care intra

	for(auto vecin : g[node]) {
		noduri_in[vecin] -= 1;
		dfs(vecin);
	}
}

int main() {
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b); // adaugam muchia (a -> b), graful fiind directionat
		// fiindca avem muchia (a -> b) care intra in b
		noduri_in[b] += 1;
	}

	// De data aceasta vom folosi un DFS

	for(int i = 1; i <= n; i++) dfs(i);

	// afisam sortarea
	for(auto nod : sortare) cout << nod << " ";
	cout << "\n";
}