省份数量 | 每日算法 · 变量语义法

📋 题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与 b 直接相连，且 b 与 c 直接相连，那么 a 与 c 间接相连。省份是一组直接或间接相连的城市。给你一个 n×n 的矩阵 isConnected，isConnected[i][j]=1 表示 i、j 直接相连。返回省份数量。

示例 1

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

输出：2

💭 模拟答题者思考

1. 问题是「连通分量计数」——天然适合并查集（Union-Find）。

2. 并查集核心操作：find（找代表元+路径压缩）、union（合并两个集合）。

3. 遍历邻接矩阵的上三角（i < j），如果 isConnected[i][j]=1 且 find(i) != find(j)，则合并，count--。

4. 最终 count 就是省份数量。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`fa[x]`	int[]	定义：元素 x 的父节点维护：初始 fa[x]=x（每个元素是一个独立的集合）更新：合并时 fa[find(x)] = find(y)
`find(x)`	int	定义：x 所属集合的代表元维护：路径压缩，返回 fa[x] 的代表元更新：递归 find(fa[x])，并 fa[x]=结果
`count`	int	定义：当前连通分量（省份）数量维护：初始 count=n 更新：每次成功合并两个集合时 count--

⌨️ 落码步骤

1. 初始化：fa[i]=i，count=n

2. 遍历 i < j：若 isConnected[i][j]==1 and find(i)!=find(j) 则合并

3. 合并：fa[find(i)] = find(j)，count--

4. 返回 count

💻 代码实现

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        fa = list(range(n))
        count = n

        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] and find(i) != find(j):
                    fa[find(i)] = find(j)
                    count -= 1

        return count

class Solution {
    vector fa;
    int count;

    int find(int x) {
        if (fa[x] != x)
            fa[x] = find(fa[x]);
        return fa[x];
    }

public:
    int findCircleNum(vector>& isConnected) {
        int n = isConnected.size();
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        count = n;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] && find(i) != find(j)) {
                    fa[find(i)] = find(j);
                    count--;
                }
            }
        }
        return count;
    }
};
// 时间 O(n²·α(n))，空间 O(n)

📈 复杂度分析

时间复杂度 O(n²·α(n)) 近似 O(n²)

空间复杂度 O(n)

⚠️ 常见坑

❗ 合并前必须检查 find(i) != find(j)，否则会重复计数 count--。

❗ 合并方向不重要（fa[find(i)]=find(j) 或反过来都可以）——没有按秩合并时尤其无所谓。

❗ 只遍历上三角即可（i < j），因为矩阵对称且对角线都是 1（自连接）。

🔍 必测边界 Case

Case 1：全不连通

isConnected = [[1,0,0],[0,1,0],[0,0,1]] → 输出 3

Case 2：全连通

isConnected = [[1,1,1],[1,1,1],[1,1,1]] → 输出 1