Cod sursa(job #3295256)

Utilizator anamarias12Serbanoiu Ana-Maria anamarias12 Data 3 mai 2025 20:01:56
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

vector<int> TopoSort(vector<vector<int>> adj, int N) {
	// vector to store the indegree
	vector<int> indegree(N);
	for(int i = 1; i <= N; i++) {
		for(int x : adj[i]) {
			indegree[x]++;
		}
	}

	// queue to store the verticles with indegree 0
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	vector<int> res;
	while(!q.empty()) {
		int crt = q.front();
		q.pop();
		res.push_back(crt);

		// decrese the indegree
		for(int i : adj[crt]) {
			indegree[i]--;
			// if it has indegree 0 now push it to the queue
			if(indegree[i] == 0)
				q.push(i);
		}
	}


	if (res.size() != N) {
        cout << "Graph contains cycle!" << endl;
        return {};
    }

    return res;
}

int main() {
	// sortarea topologica a varfurilor unui graf
	// folosind Kahn sau BFS
	// adaugam toate nodurile cu indegree 0 in coada
	// cat timp coada nu este goala scoatem un nod din coadad si decrementam indegree pt nodul dest cu 1
	// daca devine 0 il bag in coada
	// daca coada e goala si inca sunt noduri in graf, graful este ciclic si nu poate fii sortat topo
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	int N, M;
	cin >> N >> M;
	vector<vector<int>> adj(N+1);

	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}

	vector<int> res = TopoSort(adj, N);

	for (int i = 0; i < N; i ++) {
		cout << res[i] << " ";
	}

	return 0;
}