Cod sursa(job #3199410)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 1 februarie 2024 16:35:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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

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;
	}

	queue<int> q; // coada in care vom retine nodurile cu grad intern 0 (noduri_in[i] = 0)

	for(int i = 1; i <= n; i++) {
		if(noduri_in[i] == 0) 
			q.push(i);
	}

	while(!q.empty()) {
		int nod = q.front(); q.pop();
		sortare.push_back(nod); // adaugam nodul in sortare
		for(auto vecin : g[nod]) { // pentru fiecare vecin al lui nod
			noduri_in[vecin] -= 1; // scadem gradul intern cu 1 (practic, stergem nodul nod)
			if(noduri_in[vecin] == 0) // daca gradul intern devine 0
				q.push(vecin); // il adaugam in coada
		}
	}

	for(auto nod : sortare) // afisam sortarea topologica
		cout << nod << " ";
	cout << endl;
}