Advertisement
Guest User

Untitled

a guest
Nov 16th, 2011
411
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  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);
  27.     G[u].push_back(v); // add edge to adjcency list
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement