Scribd
Upload
14 views2 pages

Code 6

The document contains a C++ implementation of Kosaraju's algorithm to find the number of strongly connected components (SCCs) in a directed graph. It uses two depth-first searches (DFS) - the first to fill a stack with nodes based on finishing times, and the second on the transposed graph to count the SCCs. The main function demonstrates the algorithm with a sample directed graph defined by a list of edges.

Uploaded by

iitiananmolgupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views2 pages

Code 6

The document contains a C++ implementation of Kosaraju's algorithm to find the number of strongly connected components (SCCs) in a directed graph. It uses two depth-first searches (DFS) - the first to fill a stack with nodes based on finishing times, and the second on the transposed graph to count the SCCs. The main function demonstrates the algorithm with a sample directed graph defined by a list of edges.

Uploaded by

iitiananmolgupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <bits/stdc++.

h>
using namespace std;

class Solution {
private:
// First DFS to fill the stack in order of finishing times (post-order)
void dfs(int node, vector<int> &vis, vector<int> adj[],
stack<int> &st) {
vis[node] = 1;
for (auto it : adj[node]) {
if (!vis[it]) {
dfs(it, vis, adj, st); // explore neighbor
}
}
st.push(node); // all descendants explored, push to stack
}

// Second DFS on transposed graph to visit entire SCC


void dfs3(int node, vector<int> &vis, vector<int> adjT[]) {
vis[node] = 1;
for (auto it : adjT[node]) {
if (!vis[it]) {
dfs3(it, vis, adjT);
}
}
}

public:
// Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector<int> adj[]) {
vector<int> vis(V, 0); // visited array for original graph
stack<int> st; // stack to store vertices by finish time

// Step 1: Do DFS and store nodes in stack by finishing time


for (int i = 0; i < V; i++) {
if (!vis[i]) {
dfs(i, vis, adj, st);
}
}

// Step 2: Create the transpose of the graph


vector<int> adjT[V]; // transposed graph
for (int i = 0; i < V; i++) {
vis[i] = 0; // reset visited array for second DFS
for (auto it : adj[i]) {
// Reverse the edge direction
adjT[it].push_back(i);
}
}

// Step 3: Do DFS in the order of the stack to find SCCs


int scc = 0;
while (!st.empty()) {
int node = st.top();
st.pop();

// If not visited, it's the start of a new SCC


if (!vis[node]) {
scc++;
dfs3(node, vis, adjT);
}
}

return scc; // return the number of strongly connected components


}
};
int main() {
int n = 5;

// List of directed edges


int edges[5][2] = {
{1, 0}, {0, 2},
{2, 1}, {0, 3},
{3, 4}
};

vector<int> adj[n];

// Build adjacency list


for (int i = 0; i < n; i++) {
adj[edges[i][0]].push_back(edges[i][1]);
}

Solution obj;
int ans = obj.kosaraju(n, adj);

// Output the number of strongly connected components


cout << "The number of strongly connected components is: " << ans << endl;

return 0;
}

You might also like