Advertisement
albnayem

SCC (Strongly Connected Component)

Jul 14th, 2019
522
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. // C++ Implementation of Kosaraju's algorithm to print all SCCs
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int nodes,edges;
  6. vector <int> adj[5],transposed_adj[5];
  7.  
  8. void DFSUtil(int v, bool visited[])
  9. {
  10.     visited[v] = true;
  11.     cout << v << " ";
  12.  
  13.     vector <int>::iterator i;
  14.     for (i = transposed_adj[v].begin(); i != transposed_adj[v].end(); ++i)
  15.         if (!visited[*i])
  16.             DFSUtil(*i, visited);
  17. }
  18.  
  19. void addEdge(int v, int w)
  20. {
  21.     adj[v].push_back(w);
  22.     transposed_adj[w].push_back(v);
  23. }
  24.  
  25. void fillOrder(int v, bool visited[], stack<int> &Stack)
  26. {
  27.     visited[v] = true;
  28.  
  29.     vector <int>::iterator i;
  30.     for(i = adj[v].begin(); i != adj[v].end(); ++i)
  31.         if(!visited[*i])
  32.             fillOrder(*i, visited, Stack);
  33.  
  34.     Stack.push(v);
  35. }
  36.  
  37. void printSCCs()
  38. {
  39.     stack <int> Stack;
  40.  
  41.     bool visited[nodes];
  42.     for(int i = 0; i < nodes; i++)
  43.         visited[i] = false;
  44.  
  45.     for(int i = 0; i < nodes; i++)
  46.         if(visited[i] == false)
  47.             fillOrder(i, visited, Stack);
  48.  
  49.     for(int i = 0; i < nodes; i++)
  50.         visited[i] = false;
  51.  
  52.     while (!Stack.empty())
  53.     {
  54.         int cur = Stack.top();
  55.         Stack.pop();
  56.  
  57.         if (visited[cur] == false)
  58.         {
  59.             DFSUtil(cur, visited);
  60.             cout << endl;
  61.         }
  62.     }
  63. }
  64.  
  65. int main()
  66. {
  67.     cin>>nodes>>edges;
  68.     int v,w;
  69.  
  70.     for (int i=0;i<edges;i++)
  71.     {
  72.         cin>>v>>w;
  73.         addEdge(v,w);
  74.     }
  75.  
  76.     cout << "Following are strongly connected components in "
  77.             "given graph \n";
  78.     printSCCs();
  79.  
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement