⬅ Previous Topic
Articulation Points in GraphsNext Topic ⮕
Trie - Search⬅ Previous Topic
Articulation Points in GraphsNext Topic ⮕
Trie - SearchTopic Contents
Given a directed graph with V
vertices (numbered from 0
to V - 1
) and E
directed edges, your task is to find the number of Strongly Connected Components (SCCs).
A strongly connected component is a maximal group of vertices such that every vertex is reachable from every other vertex in the group via directed paths.
function kosarajuSCC(V, adj) {
const visited = new Array(V).fill(false);
const stack = [];
function dfs(v) {
visited[v] = true;
for (let nei of adj[v] || []) {
if (!visited[nei]) dfs(nei);
}
stack.push(v);
}
for (let i = 0; i < V; i++) {
if (!visited[i]) dfs(i);
}
const transpose = Array.from({ length: V }, () => []);
for (let u = 0; u < V; u++) {
for (let v of adj[u] || []) {
transpose[v].push(u);
}
}
visited.fill(false);
let count = 0;
function reverseDFS(v) {
visited[v] = true;
for (let nei of transpose[v]) {
if (!visited[nei]) reverseDFS(nei);
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited[node]) {
reverseDFS(node);
count++;
}
}
return count;
}
// Example usage
const graph = {
0: [1],
1: [2],
2: [0],
3: [4]
};
console.log("Number of SCCs:", kosarajuSCC(5, graph)); // Output: 2
⬅ Previous Topic
Articulation Points in GraphsNext Topic ⮕
Trie - SearchYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.