Advertisement
niamul64

NIAMUL CODE DFS//////////TROPOLOGY SORT BY DFS

Jul 17th, 2019
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. NIAMUL CODE DFS//////////TROPOLOGY SORT BY DFS
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int indegree[100]={0};
  5. vector<int> adjList[100];
  6. vector<int> topoSort;
  7.  
  8. bool impo;
  9.  
  10. #define white 0
  11. #define gry 1
  12. #define black 3
  13.  
  14. void dfs(int u,int discovered[])
  15. {
  16.     discovered[u] = gry;
  17.     int v,i;
  18.     for( i = 0; i < adjList[u].size(); ++i) {
  19.         v = adjList[u][i];
  20.         if(discovered[v]==gry)
  21.             impo=1;
  22.         if(discovered[v]==white)
  23.             dfs(v,discovered);
  24.     }
  25. discovered[u]=black;
  26.     topoSort.push_back(u);
  27. }
  28.  
  29. int main()
  30. {
  31.     impo=0;
  32.     int  discovered[100]={0};
  33.  
  34.     int n,r;
  35.     cin>>n>>r;
  36.  
  37.  
  38.     int i,j,k,l;
  39.  
  40.     int u,v;
  41.  
  42.     for(i=0;i<r;i++)
  43.     {
  44.         cin>>u>>v;
  45.         adjList[u].push_back(v);
  46.         indegree[v]++;
  47.         discovered[u]=1;
  48.         discovered[v]=1;
  49.  
  50.     }
  51.     bool fl=1;
  52.     for(i=0;i<n;i++)
  53.     {
  54.         if(indegree[i]==0)
  55.         {
  56.             fl=0;
  57.             break;
  58.         }
  59.     }
  60.     if(fl)
  61.     {
  62.         cout<<"impossible\n"<<endl;
  63.     return 0;
  64.     }
  65.     else{
  66.         for(i=0;i<n;i++)
  67.         {
  68.             if(discovered[i]==1)
  69.             {
  70.  
  71.                 dfs(i,discovered);
  72.             }
  73.         }
  74.     }
  75.      if(impo)
  76.     {
  77.         cout<<"impossible\n"<<endl;
  78.     return 0;
  79.     }
  80.     cout<<"\nsort:\n";
  81.     for(i=topoSort.size()-1;i>=0;i--)
  82.     {
  83.  
  84.         cout<<" "<<topoSort[i]<<" ";
  85.     }
  86.     cout<<"\n";
  87.  
  88.     return 0;
  89.  
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement