省份数量 图解题解

这道题到底在问什么

关系

0—1 相连，1—2 相连，3 独立

输出

2

最优解：一步一步想明白

1. 30—1、1—2 相连，那 0 和 2 也算间接相连同一省。如果手动 DFS/标记，关系一多就容易漏掉间接连通或重复数。并查集专治这种「动态合并 + 数有几组」。
2. 4转折：每个城市记一个「老大(根)」parent[i]。find = 顺着 parent 一路找到根；union(a,b) = 把 a 的根挂到 b 的根下。相连就 union 一下，最后不同根的个数 = 省份数。间接相连会自动并进同一个根，去重也免费。
3. 5parent=[0,1,2,3]，count=4开局每个城市自成一省，parent[i]=i，自己是自己的老大（颜色各不同），count = 4。关系：0—1、1—2、0—2（冗余）、3 独立。
4. 6find(0)=0, find(1)=1 不同处理 0—1：先各自 find 根。find(0)=0、find(1)=1，根不同，说明还没合并，可以并。
5. 7parent[1]=0，count=3把 1 的根挂到 0 下：parent[1]=0。0、1 同色成一组，count 减到 3。
6. 8find(1)=0, find(2)=2 不同处理 1—2：find(1) 顺着 parent 走到根 0，find(2)=2，根不同，可以并。
7. 9parent[2]=0，count=2把 2 的根（2）挂到 1 的根（0）下：parent[2]=0。0、1、2 连成一片，count = 2。注意 union 挂的是根，不是节点本身。
8. 10find(0)=find(2)=0，count 不变再遇到冗余关系 0—2：find(0)=0、find(2)=0，根相同，它俩早已同省。什么都不做，count 不变——这就是并查集自动去重的关键负例。
9. 11find(3)=3城市 3 没出现在任何关系里，没人和它 union，它的根一直是自己：find(3)=3，自成一省。
10. 12不同根 {0, 3} → 2 个省遍历每个城市求根：find(0)=find(1)=find(2)=0、find(3)=3，共 2 个不同的根 → 2 个省（{0,1,2} 和 {3}）。
11. 15凡是「动态地把元素并组、问有几组/是否连通」，并查集最快：朋友圈、连通网络、冗余连接都用它。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        def union(a, b):
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[rb] = ra
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)
        return len({find(i) for i in range(n)})

# 「动态合并、问几组 / 是否连通」都套
parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # 路径压缩(可选)
        x = parent[x]
    return x
def union(a, b): parent[find(b)] = find(a)   # 并的是"根"
# 合并所有关系后: len({find(i) for i in range(n)}) = 组数

复杂度

面试官可能追问