Number of Connected Components in an Undirected Graph — LC Medium
323. Number of Connected Components in an Undirected Graph
You have a graph of n
nodes. You are given an integer n
and an array edges
where edges[i] = [ai, bi]
indicates that there is an edge between ai
and bi
in the graph.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Constraints:
1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
- There are no repeated edges.
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
self.root = [i for i in range(n)]
for vertex1, vertex2 in edges:
self.union(vertex1, vertex2)
unique = set()
for i in self.root:
element = self.findRoot(i)
unique.add(element)
return len(unique)
def findRoot(self, target: int) -> int:
while target != self.root[target]:
target = self.root[target]
return target
def union(self, vertex1: int, vertex2: int) -> None:
root1 = self.findRoot(vertex1)
root2 = self.findRoot(vertex2)
if root1 != root2:
self.root[root2] = root1