fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define BASE 1000000007
  3. using namespace std;
  4.  
  5. vector<int> Al[1010101], Alr[1010101];
  6. vector<int> Comp[1010101];
  7. int cost[1010101];
  8. int used[1010101];
  9. vector<int> order, component;
  10. vector<vector<int> > components;
  11. vector<int> nodes;
  12.  
  13. int dfs1(int v){
  14.     used[v] = true;
  15.     for (int i=0; i<Al[v].size(); i++){
  16.         if (!used[Al[v][i]]){
  17.             dfs1(Al[v][i]);
  18.         }
  19.     }
  20.     order.push_back(v);
  21.     return 0;
  22. }
  23.  
  24. int dfs2(int v){
  25.     used[v] = true;
  26.     nodes.push_back(v);
  27.     for (int i=0; i<Alr[v].size(); i++){
  28.         if (!used[Alr[v][i]]){
  29.             dfs2(Alr[v][i]);
  30.         }
  31.     }
  32.     return 0;
  33. }
  34.  
  35. int main() {
  36. 	int n;
  37. 	cin>>n; //number of vertices
  38.  
  39. 	int m;
  40. 	cin>>m; //number of edges
  41. 	int from,to;
  42.  
  43. 	for (int i=0; i<m; i++){
  44.         cin>>from>>to;  //edges
  45.         Al[from].push_back(to);   //G
  46.         Alr[to].push_back(from);  //G_transpose
  47. 	}
  48.  
  49. 	for (int i=1; i<=n; i++){
  50.         if (!used[i]){
  51.             dfs1(i);  //mark vertices in order of finish time
  52.         }
  53. 	}
  54.  
  55. 	reverse(order.begin(), order.end());
  56. 	memset(used,0,sizeof(used));
  57.  
  58. 	for (int i=0; i<order.size(); i++){ //traverse vertices in decresing order of finish time
  59.         if (!used[i]){
  60.             nodes.clear();
  61.             dfs2(order[i]);
  62.             components.push_back(nodes);
  63.         }
  64. 	}
  65.  
  66. 	for (int i=0; i<components.size(); i++){
  67. 	    cout<<"scc "<<i+1<<" -> ";
  68.         for (int j=0; j<components[i].size(); j++){
  69.             cout<<components[i][j]<<" ";
  70.         }
  71.         cout<<"\n";
  72. 	}
  73.  
  74. }
  75.  
Success #stdin #stdout 0.04s 46840KB
comments (?)
stdin
copy 
10
12
1 2
2 3
3 1
3 4
4 5
5 6
5 7
6 4
7 3
8 9
9 10
10 9
stdout
copy 
scc 1 -> 8 
scc 2 -> 9 10 
scc 3 -> 10 
scc 4 -> 1 3 2 7 5 4 6
https://ideone.com/3uxMdo
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!