Cod sursa(job #2644185)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 23 august 2020 18:48:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> &arcs, vector<int> &inboundArcs,vector<int> &finalOrder, int currentNode) {
	if (inboundArcs[currentNode] != 0)
		return;

	inboundArcs[currentNode] = -1;
	finalOrder.push_back(currentNode);

	for(int i=0; i<arcs[currentNode].size(); ++i) {
        --inboundArcs[arcs[currentNode][i]];
        if (inboundArcs[arcs[currentNode][i]] == 0)
            dfs(arcs, inboundArcs, finalOrder, arcs[currentNode][i]);
	}
	arcs[currentNode].clear();

}



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)
			dfs(arcs, inboundArcs, finalOrder, i);

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

	return 0;

}