Cod sursa(job #2644180)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 23 august 2020 18:23:43
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

	int n, m, x, y;

	scanf("%d%d", &n, &m);

	vector<int> finalOrder;
	vector<vector<int>> arcs(n+1);
	vector<int> inboundArcs(n+1);

	for(int i=0; i<m; ++i) {
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
		inboundArcs[y] ++;
	}

	for(int i=1; i<=n; ++i) {
		if (inboundArcs[i] == 0) {
			inboundArcs[i] = -1;
			finalOrder.push_back(i);
			queue<int> q;
			q.push(i);

			while(q.size()) {
				x = q.front();
				q.pop();
				for (int j=0; j<arcs[x].size(); ++j) {
					y = arcs[x][j];
					inboundArcs[y] --;
					if (inboundArcs[y] == 0) {
						inboundArcs[y] = -1;
						finalOrder.push_back(y);
					}
					q.push(y);
				}

				arcs[i].clear();
			}
		}
	}

	for(int i = 0; i<finalOrder.size(); ++i)
		printf("%d ", finalOrder[i]);

	return 0;
}