abinash_hstu

Top Sort by Indegree

Jan 16th, 2016
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.61 KB | None | 0 0
  1. #include<cstdio>
  2. #include<vector>
  3. using namespace std;
  4. vector<int> edge[100];
  5. int indeg[100],node;
  6. void topsort()
  7. {
  8.     int i;
  9.     for(i=1;i<=node;i++)
  10.         if(indeg[i]==0)
  11.         {
  12.             indeg[i]=-1;
  13.             break;
  14.         }
  15.     if(i==node+1) return;
  16.     printf("%d ",i);
  17.     for(int j=0;j<edge[i].size();j++)
  18.         indeg[edge[i][j]]--;
  19.     topsort();
  20. }
  21. int main()
  22. {
  23.     int edges,n1,n2;
  24.     scanf("%d%d",&node,&edges);
  25.     for(int i=0;i<edges;i++)
  26.     {
  27.         scanf("%d%d",&n1,&n2);
  28.         edge[n1].push_back(n2);
  29.         indeg[n2]++;
  30.     }
  31.     topsort();
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment