leetcode_solutions/Strongly_Connected_Components.cpp at main · ar-zoop/leetcode_solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends

class Solution
{
	public:

	void dfs(int node, vector<vector<int>>& adj, int vis[], stack<int> &finTime){
	    vis[node]=1;
	    for(auto adjNode:adj[node]){
	        if(!vis[adjNode]){
	            dfs(adjNode, adj, vis, finTime);
	        }
	    }
	   finTime.push(node);
	}
	void dfs(int node, vector<vector<int>>& adj, int vis[]){
	    vis[node]=1;
	    for(auto adjNode:adj[node]){
	        if(!vis[adjNode]){
	            dfs(adjNode, adj, vis);
	        }
	    }
	}
	//Function to find number of strongly connected components in the graph.
    int kosaraju(int V, vector<vector<int>>& adj)
    {
        int vis[V]={0};
        stack<int> finTime;
        for(int i=0; i<V; i++){
            if(!vis[i]){
                dfs(i, adj, vis, finTime);
            }
        }
        vector<vector<int>> revAdj(V);
        int node;
        for(int i=0; i<V; i++){
            for(auto j: adj[i]){
                revAdj[j].push_back(i);
            }
        }
        int dfsVis[V]={0};
        int count=0;
        while(!finTime.empty()){
            node=finTime.top();
            finTime.pop();
            if(!dfsVis[node]){
                count++;
                dfs(node,revAdj,dfsVis);

            }
        }
        return count;
    }
};

//{ Driver Code Starts.


int main()
{

    int t;
    cin >> t;
    while(t--)
    {
    	int V, E;
    	cin >> V >> E;

    	vector<vector<int>> adj(V);

    	for(int i = 0; i < E; i++)
    	{
    		int u, v;
    		cin >> u >> v;
    		adj[u].push_back(v);
    	}

    	Solution obj;
    	cout << obj.kosaraju(V, adj) << "\n";
    }

    return 0;
}


// } Driver Code Ends