Advertisement
HmHimu

STRONGLY CONNECTED

Jul 20th, 2017
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char color[100];
  4. stack<int> dfs_visit(list<int>*adj,stack<int>sagor,int source)
  5. {
  6. color[source]='g';
  7. list<int>::iterator it;
  8. for(it=adj[source].begin();it!=adj[source].end();++it)
  9. {
  10. if(color[*it]=='w')
  11. {
  12. sagor=dfs_visit(adj,sagor,*it);
  13. }
  14. }
  15. color[source]='b';
  16. sagor.push(source);
  17. return sagor;
  18. }
  19. stack<int> topo(list<int>*adj,int node)
  20. {
  21. stack<int>sagor;
  22. stack<int>jerin;
  23. for(int i=1;i<=node;i++)
  24. {
  25. color[i]='w';
  26. }
  27. for(int i=1;i<=node;i++)
  28. {
  29. if(color[i]=='w')
  30. {
  31. sagor=dfs_visit(adj,sagor,i);
  32. }
  33. }
  34. return sagor;
  35. }
  36. list<int> dfs_visit1(list<int>*radj,list<int>sagor,int source)
  37. {
  38. color[source]='g';
  39. list<int>::iterator it;
  40. for(it=radj[source].begin();it!=radj[source].end();++it)
  41. {
  42. if(color[*it]=='w')
  43. {
  44. sagor=dfs_visit1(radj,sagor,*it);
  45. }
  46. }
  47. color[source]='b';
  48. sagor.push_back(source);
  49. return sagor;
  50. }
  51. list<int> scc(list<int>*radj,int node,int source)
  52. {
  53. list<int>sagor;
  54. sagor=dfs_visit1(radj,sagor,source);
  55. return sagor;
  56. }
  57. int main()
  58. {
  59. ///strongly connected components
  60. cout<<"input case numbers : ";
  61. int case1;
  62. cin>>case1;
  63. for(int temp=1;temp<=case1;temp++)
  64. {
  65. int node,edge;
  66. cout<<"input node numbers : ";
  67. cin>>node;
  68. cout<<"input edge numbers : ";
  69. cin>>edge;
  70. list<int>adj[node+1];
  71. list<int>radj[node+1];
  72. for(int tp=1;tp<=edge;tp++)
  73. {
  74. int x,y;
  75. cin>>x>>y;
  76. adj[x].push_back(y);
  77. radj[y].push_back(x);
  78. }
  79. stack<int>data;
  80. data=topo(adj,node);
  81. int mark=0;
  82. list<int>components[node+1];
  83. for(int i=1;i<=node;i++)
  84. {
  85. color[i]='w';
  86. }
  87. while(!data.empty())
  88. {
  89. if(color[data.top()]=='w')
  90. {
  91. components[++mark]=scc(radj,node,data.top());
  92. }
  93. data.pop();
  94. }
  95. for(int i=1;i<=mark;i++)
  96. {
  97. list<int>::iterator it;
  98. cout<<i<<" conponent's node : ";
  99. for(it=components[i].begin();it!=components[i].end();++it)
  100. {
  101. cout<<*it<<" ";
  102. }
  103. cout<<"\n";
  104. }
  105. }
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement