0Imagine a group of islands connected by one-way bridges. Some islands form clusters where you can travel from any island to any other within the cluster using these bridges. These clusters are like strongly connected components in a network of islands.
┌───────────────┐ ┌───────────────┐
│ A │──────▶│ B │
│ ◀────┐ │ │ │ │
└───────┘ │ └──────┘ │
│ │
▼ ▼
┌───────────┐ ┌───────────┐
│ C │◀────────│ D │
└───────────┘ └───────────┘
SCC1: A, B, C, D (all reachable within this group)
Separate vertex E with no connections forms its own SCC.from collections import defaultdict class Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def add_edge(self, u, v): self.graph[u].append(v) def _dfs(self, v, visited, stack): visited[v] = True for neighbour in self.graph[v]: if not visited[neighbour]: self._dfs(neighbour, visited, stack) stack.append(v) def _transpose(self): g = Graph(self.V) for v in self.graph: for neighbour in self.graph[v]: g.add_edge(neighbour, v) return g def _dfs_util(self, v, visited, component): visited[v] = True component.append(v) for neighbour in self.graph[v]: if not visited[neighbour]: self._dfs_util(neighbour, visited, component) def kosaraju_scc(self): stack = [] visited = [False] * self.V for i in range(self.V): if not visited[i]: self._dfs(i, visited, stack) gr = self._transpose() visited = [False] * self.V sccs = [] while stack: v = stack.pop() if not visited[v]: component = [] gr._dfs_util(v, visited, component) sccs.append(component) return sccs # Example usage if __name__ == '__main__': g = Graph(5) g.add_edge(1, 0) g.add_edge(0, 2) g.add_edge(2, 1) g.add_edge(0, 3) g.add_edge(3, 4) print(g.kosaraju_scc())
strongly connected component in a directed graph?1->2, 2->3, 3->1, 3->4, how many strongly connected components does it have?Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.