fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #define MAXN 10001
  5. using namespace std;
  6.  
  7. //ifstream fin("ctc.in");
  8. //ofstream fout("ctc.out");
  9.  
  10. class Kosaraju {
  11.  
  12.   // constructor-ul clasei
  13.   public:
  14.     Kosaraju(int N, int M): nodes( N ),
  15.                             edges( M ),
  16.                             comp( 0 ),
  17.                             Graph(2 * N + 1),
  18.                             Graph_reverse(2 * N + 1),
  19.                             isVisited(2 * N + 1),
  20.                             Results(2 * N + 1){}
  21.  
  22.   void addEdges(int x, int y) {
  23.     Graph[x].push_back(y);
  24.     Graph_reverse[y].push_back(x);
  25.   }
  26.  
  27.   void DFS(int node) {
  28.     isVisited[node] = 1;
  29.     for (vector<int>::iterator it = Graph[node].begin(); it != Graph[node].end(); ++it) {
  30.       if (!isVisited[*it]) {
  31.         DFS(*it);
  32.       }
  33.     }
  34.     Stack.push(node);
  35.   }
  36.  
  37.   void DFS_Reverse(int node) {
  38.     isVisited[node] = 1;
  39.     Results[comp].push_back(node);
  40.     for (vector<int>::iterator it = Graph_reverse[node].begin(); it != Graph_reverse[node].end(); ++it) {
  41.       if (!isVisited[*it]) {
  42.         DFS_Reverse(*it);
  43.       }
  44.     }
  45.     Stack.push(node);
  46.   }
  47.  
  48.   // kosaraju in action
  49.   void solve() {
  50.     int vertex = 0;
  51.     for (int i = 1; i <= nodes; i++)
  52.       if (!isVisited[i]) {
  53.         DFS(i);
  54.       }
  55.     for (int v = 1; v <= nodes + 1; v++) isVisited[v] = 0;
  56.     while (!Stack.empty()) {
  57.       vertex = Stack.top();
  58.       Stack.pop();
  59.       if (!isVisited[vertex]) {
  60.         comp++;
  61.         DFS_Reverse(vertex);
  62.       }
  63.     }
  64.   }
  65.  
  66.   void writeData() {
  67.     // Scriem numarul de componente tare conexe
  68.     cout << comp << '\n';
  69.  
  70.     for (int i = 1; i <= comp; i++) {
  71.       for (vector<int>::iterator it = Results[i].begin(); it != Results[i].end(); ++it) {
  72.         cout << *it << " ";
  73.       }
  74.      cout << '\n';
  75.     }
  76.   }
  77.  
  78.   private:
  79.     int nodes, edges, comp;
  80.     vector<vector<int>> Graph;
  81.     vector<vector<int>> Graph_reverse;
  82.     vector<vector<int>> Results;
  83.     vector<int> isVisited;
  84.     stack<int> Stack;
  85. }; // end class Kosaraju
  86.  
  87.  
  88. int main() {
  89.   int n, // nr de noduri
  90.       m, // nr de arce
  91.       x, // doua noduri
  92.       y; //
  93.   cin >> n >> m;
  94.   Kosaraju ob(n,m);
  95.   for (int i = 1; i <= m; i++) {
  96.     cin >> x >> y;
  97.     ob.addEdges(x,y);
  98.   }
  99.  
  100.   //fin.close();
  101.   ob.solve();
  102.   ob.writeData();
  103.   return 0;
  104. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
8 12
1 2
2 6
6 7
7 6
3 1
3 4
2 3
4 5
5 4
6 5
5 8
8 7
stdout
copy 
2
1 3 2 
6 7 8 5 4
https://ideone.com/JwVnCp
Kosaraju's algorithm
language:
C++14 (clang 8.0)
created:
262 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!