Strongly Connected Components - SCC


  1. #include<bits/stdc++.h>
  2. using namespace std;

  3. vector<int>adj[100],rev[100];

  4. bool visited[1000];

  5. stack<int>stk;

  6. void DFS(int s)
  7. {
  8. if(visited[s])
  9. return;
  10. visited[s]=1;
  11. for(int i=0;i<adj[s].size();i++)
  12. DFS(adj[s][i]);
  13. stk.push(s);
  14. }

  15. void DFS2(int s) {
  16. if(visited[s]==2){
  17. cout<<endl;
  18. return;
  19. }
  20. cout<<s<<" ";
  21. visited[s]=2;
  22. for(int i=0;i<rev[s].size();i++)
  23. DFS2(rev[s][i]);
  24. }

  25. int main() {
  26. int n,e,a,b;
  27. cin>>n>>e;
  28. for(int i=0;i<e;i++){
  29. cin>>a>>b;
  30. adj[a].push_back(b);
  31. rev[b].push_back(a);
  32. }
  33. for(int i=1;i<=n;i++){
  34. if(!visited[i])
  35. DFS(i);
  36. }
  37. while(!stk.empty()){
  38. int x=stk.top();
  39. stk.pop();
  40. DFS2(x);
  41. cout<<endl;
  42. }
  43. cout<<endl;

  44. return 0;
  45. }
  46. /*
  47. input

  48. 8 7
  49. 1 2
  50. 2 5
  51. 1 6
  52. 2 7
  53. 2 4
  54. 1 3
  55. 5 8
  56. output: 1 3 6 2 4 7 5 8
  57. */

No comments

Theme images by Jason Morrow. Powered by Blogger.