HmHimu

topological sort(directed graph_circle check)

Jul 20th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int v;
  6. int adj[100][100];
  7. char color[100];
  8. stack<int> s;
  9. int cir=0;
  10.  
  11. void visit_dfs(int u)
  12. {
  13.  
  14.  
  15. color[u]='g';
  16.  
  17.  
  18. for(int i=1;i<=v;i++)
  19. {
  20. if(adj[u][i]==1 && color[i]=='w')
  21. {
  22. visit_dfs(i);
  23. }
  24. if(adj[u][i]==1 && color[i]=='g')
  25. {
  26. cir++;
  27. }}
  28. color[u]='b';
  29. s.push(u);
  30.  
  31. }
  32. void dfs()
  33. {
  34. if(cir==0)
  35. {
  36. for(int i=1;i<=v;i++)
  37. {
  38. color[i]='w';
  39. }
  40.  
  41. for(int i=1;i<=v;i++)
  42. {
  43. if(color[i]=='w')
  44. {
  45. visit_dfs(i);
  46. }
  47. }
  48. }
  49. else{
  50. cout<<"circle exit";
  51. }
  52. }
  53. int main()
  54. {
  55. int a,b;
  56.  
  57. cout<<" Enter number of vartex : ";
  58. cin>>v;
  59.  
  60. while(cin>>a>>b && a!=0 && b!=0)
  61. {
  62. adj[a][b]=1;
  63. }
  64.  
  65. dfs();
  66.  
  67. while(!s.empty())
  68. {
  69. cout<<s.top()<<"-> ";
  70. s.pop();
  71. }
  72. }
Advertisement
Add Comment
Please, Sign In to add comment