Problem-
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, Find the number of strongly connected components in the graph.
i am solving this on geeksforgeeks. I have two codes. I do not know the difference because they use the same logic and implementation.
First code
void dfs(int node, vector<vector<int>>& adj, stack<int>& st, vector<bool>& vis) {
vis[node] = 1;
for (auto &it : adj[node]) {
if (!vis[it]) dfs(it, adj, st, vis);
}
st.push(node);
}
void dfs2(int node, vector<vector<int>>& adj, vector<bool>& vis) {
vis[node] = 1;
for (auto &it : adj[node]) {
if (!vis[it]) dfs2(it, adj, vis);
}
}
int kosaraju(int V, vector<vector<int>>& adj) {
vector<bool> vis(V, 0);
stack<int> st;
// First DFS to fill the stack with the finishing times
for (int i = 0; i < V; i++) {
if (!vis[i]) dfs(i, adj, st, vis);
}
// Create the transpose of the graph
vector<vector<int>> adjRev(V);
for (int i = 0; i < V; i++) {
for (auto &it : adj[i]) {
adjRev[it].push_back(i);
}
}
// Second DFS to count the number of SCCs
int cnt = 0;
vis = vector<bool>(V, 0);
while (!st.empty()) {
int node = st.top();
st.pop();
if (!vis[node]) {
dfs2(node, adjRev, vis);
cnt++;
}
}
return cnt;
}
this is running properly and passed all test cases.
Second code-
private:
int dfs(int v, stack<int> &s, vector<int> &vis, vector<vector<int>> g){
vis[v] = 1;
for(auto child : g[v]){
if(vis[child] == 0){
dfs(child, s, vis, g);
}
}
s.push(v);
}
int DFS(int v, vector<int> &vis, vector<vector<int>> g){
vis[v] = 1;
for(auto child : g[v]){
if(vis[child] == 0){
DFS(child, vis, g);
}
}
}
public:
//Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector<vector<int>>& adj)
{
stack<int> s;
vector<int> vis(V, 0);
for(int i =0; i<V; i++){
if(vis[i] == 0) dfs(i, s, vis, adj);
}
vector<vector<int>> g(V);
for(int i =0; i<V; i++){
vis[i] =0;
for(auto y : adj[i]){
g[y].push_back(i);
}
}
int ct =0;
while(!s.empty()){
int x = s.top();
s.pop();
if(vis[x] == 0){
DFS(x, vis, g);
ct++;
}
}
return ct;
}
This is giving error- Time Limit Exceeded.
I am not able to find the difference between these two codes. Anyone please explain it.