kosaraju's algorithm
//by YASH DHOKIA //strongly connected components in graph using kosaraju's algorithm //implementation of kosaraju's algorithm using adjacency list #include<bits/stdc++.h> using namespace std; void addedge(vector<int> graph[],int u1,int u2) { graph[u1].push_back(u2); } void DFSrec(vector<int> graph[],vector<bool> &visited,stack<int>&st,int u) { visited[u]=true; for(int k=0; k<graph[u].size(); k++) { if( !visited[graph[u][k]] ) { DFSrec(graph,visited,st,graph[u][k]); } } st.push(u); } void DFS(vector<int> tran[],vector<bool> &visited,int x) { visited[x]=true; cout<<x<<" "; for( int k=0; k<tran[x].size(); k++ ) { if( !visited[tran[x][k]] ) { DFS(tran,visited,tran[x][k]); } } } void kosaraju(vector<int> graph[],int v) { vector<bool> visited(v,false); stack<int>st; for(int i=0; i<v; i++) { if( !visited[i] ) DFSrec(graph,visited,st,i); } vector<int> tran[v]; for(int i=0; i<v; i++) { visited[i]=false; for(int j=0; j<graph[i].size(); j++) { tran[graph[i][j]].push_back(i); } } int count=1; while(!st.empty()) { int x=st.top(); st.pop(); if(!visited[x]) { cout<<"component " << count++ << ": "; DFS(tran,visited,x); cout<<endl; } } } int main() { int v,e; cin>>v>>e; vector<int> graph[v]; for(int i=0; i<e; i++) { int u1,u2; cin>>u1>>u2; addedge(graph,u1,u2); } kosaraju(graph,v); return 0; } /* sample input 1: 5 6 0 1 1 2 1 3 2 1 3 4 4 3 sample input 2: 5 5 0 1 1 2 1 3 2 0 3 4 sample input 3: 11 17 0 2 0 3 1 0 1 10 2 4 3 2 4 3 5 3 5 6 6 4 6 7 7 8 8 5 9 1 10 5 10 8 10 9 */