• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Nov 16th, 2011 225 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cstdio>
2. #include <algorithm>
3. #include <vector>
4. #include <queue>
5. using namespace std;
6.
7.
8. const int MX = 100007; // maximum number of nodes in the graph.
9. int n,m,u,v;
10. vector<int> G[MX]; // adjacency list.
11. int in[MX];
12.
13. vector<int> TS; // the output vector with nodes sorted in topological order.
14.
15.
16. int main() {
17.   /* Input format:
18.      n - number of nodes
19.      m - number of edges
20.      we assume nodes are enumbered 1..n
21.      next m lines contains edges descriptions
22.      represented as a pair of integers.
23.   */
24.   scanf("%d %d", &n, &m);
25.   while(m--) {
26.     scanf("%d %d", &u, &v);
28.     in[v]++; // increase input order of v
29.   }
30.   // Add all the nodes with zero input order to the awswer.
31.   for(int i=1; i<=n; ++i) if(in[i]==0) TS.push_back(i);
32.   // For every noded that we added to the Topological Order so far:
33.   for(int i=0; i<TS.size(); ++i) {
34.     int current_node = TS[i];
35.     // for every edge foing out of current_node (current_node->neighbour).
36.     for(int j = 0; j<G[current_node].size(); ++j) {
37.       int neighbour = G[current_node][j];
38.       // Decrease input order of neighbour ("delete" edge).
39.       in[neighbour]--;
40.       // If input order of the neighbour is 0 add it to anwser.
41.       if(in[neighbour] == 0) TS.push_back(neighbour);
42.     }
43.   }
44.   // Print the anwser out.
45.   for(int i=0; i<TS.size(); ++i)
46.     printf("%d ", TS[i]);
47.   printf("\n");
48. }
49.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top