Cod sursa(job #2313260)

Utilizator KaryamKaryam Ahmad Karyam Data 6 ianuarie 2019 15:22:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
/* Kahn's algorithm for finding the topological order
   --------------------------------------------------
   	- topological order is only possible for DAG
		- there can be more then one topological ordering
	This approach is based on the following fact
    ---------------------------------------------
    - a DAG has at least one vertex with in-degree 0 and one vertex with out-degree 0
*/

#include <bits/stdc++.h>
using namespace std;
FILE *fin  = freopen("sortaret.in", "r", stdin);
FILE *fout = freopen("sortaret.out", "w", stdout);

const int nmax = 5e4+3;

struct Graph {
	int nodes;
	vector <vector<int>> adj;
	Graph(int n) : nodes(n), adj(n+1) { }
	void add_edge(int from, int to) {
		adj[from].push_back(to);
	}
};

queue <int> q;

vector <int> topological_sort(Graph g) {
	vector <int> degree(g.nodes+1);
	vector <int> order;

	for (int from = 1; from <= g.nodes; ++ from)
		for (int to : g.adj[from])
			degree[to] ++;

	for (int node = 1; node <= g.nodes; ++ node)
		if (degree[node] == 0)
			q.push(node);

	while (! q.empty()) {
		int u = q.front();
		order.push_back(u);
		q.pop();

		for (int v : g.adj[u])
			if(!--degree[v])
				q.push(v);
	}
	return order;
}

int main() {
	int n, m;
	cin >> n >> m;
	Graph g(n);
	for (; m > 0; -- m) {
		int from, to;
		cin >> from >> to;
		g.add_edge(from, to);
	}
	vector <int> order = topological_sort(g);
	for (int node : order)
		cout << node << " ";
	return 0;
}