Advertisement
sakib_shahriyar

Strongly Connected Component

Feb 27th, 2017
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-STRONGLY_CONNECTED_COMPONENT*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. vector<int > adj[10];//Adjency List Representation
  5. vector<int> adj_rev[10];
  6. bool visit[10];
  7. stack <int > mystack;
  8.  
  9. void set_false()
  10. {
  11.     for(int i=0;i<10;i++)
  12.         visit[i]=false;//Mark visit array as False;
  13. }
  14. void dfs_order(int s)
  15. {
  16.     visit[s]=true;
  17.     for(int i=0;i<adj[s].size();++i)
  18.             if(visit[adj[s][i]]==false)    
  19.                 dfs_order(adj[s][i]);
  20.     mystack.push(s);
  21. }
  22. void dfs(int s)
  23. {
  24.     visit[s]=true;
  25.     cout<<s<<" ";
  26.     for(int i=0;i<adj_rev[s].size();++i)
  27.             if(visit[adj_rev[s][i]]==false)  
  28.              dfs(adj_rev[s][i]);
  29.  
  30.  
  31. }
  32. int main()
  33. {
  34.     int node,edge,x,y,c=0;
  35.     cin>>node>>edge;
  36.     set_false();
  37.     for(int i=0;i<edge;i++)
  38.     {
  39.      cin>>x>>y;
  40.      adj[x].push_back(y);
  41.      adj_rev[y].push_back(x);//Reverse of given graph
  42.     }
  43.  
  44.  for(int i=1;i<=node;i++)
  45.  if(visit[i]==false)
  46.    dfs_order(i); // vertices in order of completion of the recursive calls.
  47.  
  48.    set_false();
  49.    while(!mystack.empty())
  50.    {
  51.    int v=mystack.top();
  52.      mystack.pop();
  53.      if(visit[v]==false)
  54.      {
  55.         dfs(v);
  56.         c++;
  57.         cout<<"\n";
  58.      }
  59.    }
  60.    cout<<"Number of Components :"<<c;
  61. }
  62. /*
  63. 4 5
  64. 1 2
  65. 2 3
  66. 3 1
  67. 1 4
  68. 3 4  
  69. out: 1 3 2
  70. 4
  71. Number of Components :2
  72. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement