Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <queue>
- using namespace std;
- const int MX = 100007; // maximum number of nodes in the graph.
- int n,m,u,v;
- vector<int> G[MX]; // adjacency list.
- int in[MX];
- vector<int> TS; // the output vector with nodes sorted in topological order.
- int main() {
- /* Input format:
- n - number of nodes
- m - number of edges
- we assume nodes are enumbered 1..n
- next m lines contains edges descriptions
- represented as a pair of integers.
- */
- scanf("%d %d", &n, &m);
- while(m--) {
- scanf("%d %d", &u, &v);
- G[u].push_back(v); // add edge to adjcency list
- in[v]++; // increase input order of v
- }
- // Add all the nodes with zero input order to the awswer.
- for(int i=1; i<=n; ++i) if(in[i]==0) TS.push_back(i);
- // For every noded that we added to the Topological Order so far:
- for(int i=0; i<TS.size(); ++i) {
- int current_node = TS[i];
- // for every edge foing out of current_node (current_node->neighbour).
- for(int j = 0; j<G[current_node].size(); ++j) {
- int neighbour = G[current_node][j];
- // Decrease input order of neighbour ("delete" edge).
- in[neighbour]--;
- // If input order of the neighbour is 0 add it to anwser.
- if(in[neighbour] == 0) TS.push_back(neighbour);
- }
- }
- // Print the anwser out.
- for(int i=0; i<TS.size(); ++i)
- printf("%d ", TS[i]);
- printf("\n");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement