27.Kosaraju's Algorithm.md

Kosaraju's Algorithm

Helps tto find all the strongly connected components in the directed graph

Strongly Connected com

• In strongly connected components, every node will be reachable to every other node

• 

• in the above graph G1, there are total 3 SCC(strongly connected components) first is {1, 2, 3}(order does not matter), second is {4} and third is {5}, 4 and 5 are not stronly connected bcz we can go from 4 to 5 but not from 5 to 4

  steps

  • You've to sort all the nodes in order of finishing time - we know that this can be only done by Topo Sort - O(N)
  • Transpose the graph, i.e reverse the direction if edges - O(N+E)
  • Do the DFS according to the finishing time, i.e whatever we have store in the stack - O(N+E)

• T.C = O(N) for topo sort + O(N +E) for transpose + O(N +E) for DFS = O(N +E)

• S.C = O(N +E) to store the transpose graph + O(N) for visited array + O(N) for stack = O(N +E)

code

• take care when converting from vector of vector of edges to adjacency list - loop will go upto the size of the edges i.e edges.size() and not upto the size of the vertex(frequent + silly mistake)
• in topo sort, the vertex will be pushed in the stack in the last

#include<bits//stdc++.h>
using namespace std;

void revDfs(int src, vector<int> &tempAns, vector<int> &vis, vector<int> transpose[]){
    vis[src] = 1;
    tempAns.push_back(src);
    
    for(auto it : transpose[src]){
        if(!vis[it]){
            revDfs(it, tempAns, vis, transpose);
        }
    }

}
void topoDfs(int src, vector<int> &vis, vector<int> adj[], stack<int> &st){
    vis[src] = 1;
    for(auto it : adj[src]){
        if(!vis[it]){
            topoDfs(it, vis, adj, st);
        }
        
    }
    st.push(src);
}
vector<vector<int>> stronglyConnectedComponents(int n, vector<vector<int>> &edges)
{
    // Write your code here.
    vector<int> adj[n];

    for(int i=0; i<edges.size(); i++){
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u].push_back(v);
    }
    
    vector<int> vis(n, 0);
    stack<int> st;
    for(int i=0; i<n; i++){
        if(!vis[i]){
            topoDfs(i, vis, adj, st);
        }
    }

    vector<int> transpose[n];

    for(int i=0; i<n; i++){
        vis[i] = 0;
        for(auto it: adj[i]){
            transpose[it].push_back(i);
        }
    }
    vector<vector<int>> ans;
    int count=0;
    while(!st.empty()){
        int node = st.top();
        st.pop();

        if (!vis[node]) {
            vector<int> tempAns; 
            revDfs(node, tempAns, vis, transpose);
            ans.push_back(tempAns);
        }
    }
    
    return ans;

}