mirror of
https://github.com/prdlk/leetcode.git
synced 2026-11-02 21:22:43 +00:00
70 lines
1.6 KiB
Python
70 lines
1.6 KiB
Python
"""
|
|
323. Number of Connected Components in an Undirected Graph
|
|
Difficulty: Medium
|
|
https://leetcode.com/problems/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] = [ai, bi]
|
|
|
|
• ai != bi
|
|
|
|
• There are no repeated edges.
|
|
"""
|
|
|
|
|
|
class Solution:
|
|
def countComponents(self, n: int, edges: list[list[int]]) -> int:
|
|
par = [i for i in range(n + 1)]
|
|
rank = [1] * (n + 1)
|
|
|
|
def find(n):
|
|
res = n
|
|
while res != par[res]:
|
|
par[res] = par[par[res]]
|
|
res = par[res]
|
|
return res
|
|
|
|
def union(n1, n2):
|
|
p1, p2 = find(n1), find(n2)
|
|
if p1 == p2:
|
|
return 0
|
|
if rank[p1] > rank[p2]:
|
|
par[p2] = p1
|
|
rank[p1] += rank[p2]
|
|
else:
|
|
par[p1] = p2
|
|
rank[p2] += rank[p1]
|
|
return 1
|
|
|
|
res = n
|
|
for n1, n2 in edges:
|
|
res -= union(n1, n2)
|
|
return res
|