Advertisement
Riz1Ahmed

Topological Sort (UVA Ordering task)

Feb 19th, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. /** Topological Sort (UVA-10305 Ordering task) ***
  2. You are given N task. You must complete task U before V.
  3. Print the Possible order of task.
  4. Input: 3 3 nl 1 2 nl 1 3 nl 3 2. Output: 1 3 2 (nl=NewLine)*/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. vector<int> vc;
  8. void DFS(int x, vector<int> *g, int *done){
  9.     for (int i=0; i<g[x].size(); i++)
  10.         if (!done[g[x][i]])
  11.             DFS(g[x][i],g,done);
  12.     vc.push_back(x);
  13.     done[x]=1;
  14.     return;
  15. }
  16. int main(){
  17.     int n,e,u,v,i;
  18.     while (~scanf("%d %d",&n,&e)){
  19.         int c=0, done[n+5];
  20.         memset(done,0,sizeof(done));
  21.         vector<int> g[n+5];
  22.         vc.clear();
  23.         for (i=0; i<e; i++){
  24.             cin>>u>>v, g[v].push_back(u);
  25.         }
  26.         for (i=1; i<=n; i++)
  27.             if (!done[i])
  28.                 DFS(i,g,done);
  29.         for (i=0; i<vc.size(); i++)
  30.             printf(i!=vc.size()-1 ? "%d ":"%d\n",vc[i]);
  31.     }
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement