323. Number of Connected Components in an Undirected Graph
难度: 中等
刷题内容
原题连接
- https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph
内容描述
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 1
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
解题方案
思路 1
经典并查集题目，可以去总结部分先看看并查集的概念已经优化
class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
def find(x):
# if uf[x] != x:
# uf[x] = find(uf[x])
while x != uf[x]:
uf[x] = uf[uf[x]]
x = uf[x]
return uf[x]
def union(x, y):
x_root = find(x)
y_root = find(y)
uf[x_root] = y_root
uf = [i for i in range(n)]
for (node1, node2) in edges:
union(node1, node2)
res = set([find(i) for i in range(n)])
return len(res)
