前几天整理刷题流水账的时候看到自己备注栏里写着一行标题2026年--Lc337-547. 省份数量(图--java版。熟悉LeetCode的朋友应该一眼就认出来了前半部分可能是上一个题的编号串在一起了真正的主角是547. Number of Provinces省份数量官方分类在图论Tag下经典程度不亚于岛屿问题系列。这道题在近几年的笔试和面试里出现频率相当高尤其是Java岗位候选人几乎人手一刷。这题表面给了个二维矩阵isConnected说的是城市之间的直接连接关系让统计有多少个省份。听着像数学题其实是一道不折不扣的无向图连通分量计数问题。解法无非三条路DFS、BFS、并查集。今天我就把这三种Java写法全部拆开讲顺便把面试追问、常见坑、延伸题目一次性说透。1. 一道送分题为什么每年都有人卡在矩阵转图这一步1.1 题意到底说了什么原题描述可以这么理解有n个城市编号从0到n-1。给你一个n x n的二维矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连0表示没有直接相连。一个省份的定义是一组直接或间接相连的城市并且组内不包含与组外城市相连的城市。翻译成人话就是——把直接相连和间接相连的关系全部打通能互相到达的城市属于同一个省完全孤立的城市自己就是一个省。题目最后要你返回省份的总数量。看官方给的两个例子会更直观。示例一isConnected [ [1,1,0], [1,1,0], [0,0,1] ]这里城市0和城市1直接相连城市2谁也不连所以答案是2。示例二isConnected [ [1,0,0,1], [0,1,1,0], [0,1,1,1], [1,0,1,1] ]矩阵里0和3相连1和2相连2和3又相连结果四个城市全在一个连通块里答案就是1。很多人看到这个题的直觉是这不该用二维数组BFS吗——确实可以但先别急着遍历矩阵的每个格子第一步必须把矩阵和图的对应关系想清楚否则后面写循环很容易把行列搞混。1.2 邻接矩阵就是一张现成的图isConnected本身就是一张邻接矩阵这是图论里最直观的存储方式之一。图的每个节点就是一个城市节点的编号就是矩阵的行下标/列下标isConnected[i][j]表示节点i到节点j有没有一条边。注意三个细节对角线isConnected[i][i]全部是1表示每个城市只跟自己相连这没什么实际意义遍历时可以直接忽略如果按无向图理解矩阵必然是对称矩阵即isConnected[i][j] isConnected[j][i]矩阵里每个值要么是0要么是1不用考虑权重。判断间接相连本质上就是看两个节点在图上能不能通过一条路径到达。isConnected[0][2]是0但如果0能到1、1又能到2那0和2依然属于同一个连通分量。这正是图遍历或者并查集能解决的问题。1.3 这道题的本质数连通分量把城市看成点、连接关系看成边之后题目的问题就变成了这张图上到底有几个连通分量。连通分量是图论里的基础概念一个连通分量就是图中极大的一组节点这组节点内部任意两点之间都有路径相连并且这个集合没法再加入其他节点。在这个算法题里一个省份就是一个连通分量。数连通分量这件事在算法题里几乎长成了一个固定套路搞一个数组/集合记录节点是否被访问过从头扫所有节点没被访问过就进入新一轮搜索DFS或BFS每进入一轮新搜索计数器加一搜索过程中把能走到的节点全部标记为已访问。这套思路不仅能解省份数量所有数连通块的题比如岛屿数量底层逻辑都是一模一样的。2. 解法一DFS染色法三分钟写出来的直观答案2.1 遍历逻辑每个人只能被访问一次DFS解法是三类解法里最容易让新手理解的。思路很简单准备一个boolean[] visited长度是n初始都是false从0号城市开始逐个检查如果某个城市i还没有被访问过说明它属于一个新的连通分量provinces从城市i开始深度优先搜索把整个连通分量里的所有城市全部标记成visited true继续看下一个城市直到所有城市都被访问过。关键点只有一个进入新城市的那一刻要先标记再递归。很多人写图DFS容易犯进了递归才标记或者先递归又标记的顺序错误导致同一个节点被重复入栈甚至死循环。2.2 Java代码实现与注意点直接给出完整实现。这是我个人习惯的写法简单、稳、不容易出边界问题class Solution { public int findCircleNum(int[][] isConnected) { int n isConnected.length; boolean[] visited new boolean[n]; int provinces 0; for (int i 0; i n; i) { if (!visited[i]) { provinces; dfs(isConnected, visited, i); } } return provinces; } private void dfs(int[][] isConnected, boolean[] visited, int city) { // 当前城市已经进入搜索栈立刻标记 visited[city] true; for (int j 0; j isConnected.length; j) { if (isConnected[city][j] 1 !visited[j]) { dfs(isConnected, visited, j); } } } }有几个细节值得说dfs里没有提前写if (visited[city]) return;因为调用dfs的地方已经保证传进来的节点是没被访问过的多写一步也不算错只是会让代码显得啰嗦for循环要遍历完整的n列不能只从city1开始否则city走向之前编号较小的城市时会漏掉对角线i j时判断isConnected[city][city] 1 !visited[city]由于visited[city]已经为true这个分支走不进去所以不用特殊处理。2.3 复杂度与潜在风险时间复杂度是O(n^2)。因为最坏情况下每个节点都要扫一遍它对应的那一整行行的长度是n所以整体是平方复杂度。空间复杂度是O(n)来自visited数组和系统递归调用栈递归深度最坏为n。n的范围在原题里一般是1 n 200所以递归深度最多200层完全不用担心栈溢出问题。但如果题目改造成大图比如n到一万DFS递归就会有栈溢出的风险这时候优先考虑下面要说的并查集或者BFS。还有一个容易被忽略的点如果面试官要求你不能修改输入矩阵DFS数组解法完全满足如果题目放宽让你原地标记也有人直接拿isConnected[i][i] 0当visited用但这属于奇技淫巧不推荐在面试里秀容易把代码搞难懂。3. 解法二并查集把谁和谁是一伙交给树来管3.1 为什么并查集是图连通题的亲儿子DFS和BFS是从起点出发把所有邻居都走一遍并查集是另一种思路我不关心路径是怎么走的我只关心两个节点在不在同一个集合里。并查集Union-Find本质上是维护若干棵树的数组结构。每个节点都有一个根节点同一个根下面的所有节点属于同一个集合。初始时每个节点的根就是自己也就是n个独立集合只要发现isConnected[i][j] 1就把i和j合并到同一个集合最后数一数还剩多少个根就是多少个省份。这个思路在处理动态连接的问题上有天然优势因为它不需要真的把整张图遍历一遍只需要把每条边交给并查集处理就行。3.2 路径压缩与按秩合并两个优化缺一不可如果只写最基础的find和union最坏情况下并查集可能退化成一个长链find一次要沿着链走到头性能堪忧。所以两个优化是必须掌握的路径压缩在find里找到根节点之后把路径上经过的节点的父节点直接指向根。这样下次再查这些节点一步就能找到根。我习惯用递归式路径压缩。按秩合并union的时候比较两棵树的高度秩把矮一点的树挂到高一点的树下避免树越来越高。这里可以用rank数组记录树的高度两个根如果高度一样合并后高度加一。两个优化都做了之后单次操作的时间复杂度几乎可以认为是常数级别整体复杂度是O(n^2 * α(n))其中α是反阿克曼函数实际运行中极小可以当成O(n^2)看待。3.3 完整Java实现class Solution { public int findCircleNum(int[][] isConnected) { int n isConnected.length; UnionFind uf new UnionFind(n); // 只遍历矩阵上三角避免重复合并 for (int i 0; i n; i) { for (int j i 1; j n; j) { if (isConnected[i][j] 1) { uf.union(i, j); } } } return uf.count(); } } class UnionFind { private int[] parent; private int[] rank; private int count; public UnionFind(int n) { parent new int[n]; rank new int[n]; count n; for (int i 0; i n; i) { parent[i] i; } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } public int count() { return count; } }这里有个小优化值得单独说主循环里j从i 1开始只遍历矩阵的上三角。因为无向图的邻接矩阵是对称的isConnected[i][j]和isConnected[j][i]表示同一条边重复合并没有任何意义。这个习惯放在像本题这种边长很大的场景里能少一半的无用操作。3.4 只遍历半个矩阵的小优化我刚接触这题时是个急性子写了两层for循环直接j 0开始遍历结果发现并查集里大量union都是冗余的。后来自己跑了一遍示例就意识到对称矩阵的另一半就是同一批关系。因此判断 要不要读j 0到n-1 这种问题第一反应应该看图的类型有向图矩阵往往不对称必须把每个i - j当成一条独立边处理无向图一条边只需要处理一次处理i j的那一半就够了。这个细节面试官有时会专门问答上来就是加分项。4. 解法三BFS队列版与其他方案的取舍对比4.1 队列版实现BFS解法的框架和DFS几乎一样无非是把递归栈换成了显式的队列在 Java 里用ArrayDeque效率最高别用LinkedList当队列用。class Solution { public int findCircleNum(int[][] isConnected) { int n isConnected.length; boolean[] visited new boolean[n]; int provinces 0; DequeInteger queue new ArrayDeque(); for (int i 0; i n; i) { if (!visited[i]) { provinces; visited[i] true; queue.offer(i); while (!queue.isEmpty()) { int city queue.poll(); for (int j 0; j n; j) { if (isConnected[city][j] 1 !visited[j]) { visited[j] true; queue.offer(j); } } } } } return provinces; } }BFS跟DFS在时间复杂度上没有本质区别都是O(n^2)。区别在于空间BFS的队列在最坏情况下可能同时承载多个节点但依然受限于n所以空间也是O(n)。对于这道题BFS最大的好处是没有递归栈溢出的风险如果面试官故意把输入范围说得很大BFS比DFS稳。4.2 三种解法横向对比为了看得清楚我把三种方式放在一起对比解法核心思路时间复杂度空间复杂度代码量推荐场景DFS递归染色遍历每个连通块O(n^2)O(n) 栈空间少快速AC、n较小BFS队列逐层扩散O(n^2)O(n)少避免递归、n较大并查集连通关系合并数根节点O(n^2 * α(n))O(n)中需要后续继续合并/查找对于这道题三者都能顺利通过。但在面试中我的建议是如果只能写一种优先并查集因为它的模板复用价值最高。很多图论题、字符串分组题、冗余连接题直接套并查集就能解。DFS适合作为第一反应快速给出可运行答案BFS适合在大数据量下求稳妥。4.3 面试官追问时怎么答这道题出现在面试中时面试官大概率会在你给出一种解法后追加几个问题你觉得这个矩阵如果非常大比如n 10000你的解法还能过吗——DFS可能会栈溢出优先选BFS或并查集如果城市之间的连接关系不是一次性给全而是不断追加怎么办——这显然指向并查集因为它支持动态合并你能不能再想想空间能不能更省——其实visited数组已经是O(n)输入矩阵本身没办法压缩可以回答在给定邻接矩阵的前提下O(n)空间已经是下限。对这类追问不要慌核心就是表达出我知道每种方法的适用边界。5. 这题的坑和考点延伸从省份数量看并查集家族5.1 我踩过的三个坑刷题少的时候我在这个题上真的翻过车记忆犹新。第一个坑是visited标记时机。我最早写DFS时习惯在递归开头写if (visited[i]) return;然后在入递归之后才把当前节点置为true。问题在于如果两个节点相互指向比如0 - 1、1 - 0递归还没返回的时候两个节点已经互相入栈虽然最终不会死循环但会多很多无意义的递归调用。后来我改成进入节点立即标记代码干净多了跑测试样例也更快。第二个坑是并查集的find写成了迭代式但忘了路径压缩。有段时间我图省事find写了个while循环只做parent[x] parent[parent[x]]这个叫隔代压缩其实也可以但务必意识到它比递归版多几次跳转。最怕的就是既没递归压缩也没隔代压缩直接while (parent[x] ! x) x parent[x];这种写法在最坏情况下会退化性能跟链表差不多。第三个坑更隐蔽主函数遍历矩阵时没有跳过i j的对角线。理论上它不影响正确性因为自环不会造成合并但在调试时很容易让你误以为是不是合并逻辑写错了白白浪费几分钟。建议直接j i 1跳过下三角和主对角线逻辑更清爽。5.2 衍生题目一网打尽省份数量属于连通分量题型里最基础的一道。刷完它建议立刻顺着同一个模板往下做这几道200. 岛屿数量同样是数连通分量网格版的DFS/BFS注意方向数组的写法1319. 连通网络的操作次数需要利用边数 节点数 - 连通分量数这个公式处理需要多少次操作才能让所有设备连通684. 冗余连接并查集的经典应用往图里不断加边发现某条边的两个端点已经在同一个集合里那这条边就是冗余边990. 等式方程的可满足性把变量之间的相等关系合并再检查不等关系是否冲突323. 无向图中连通分量的数量这道题是力扣的会员题思路跟省份数量完全一致只是输入换成了边列表。我个人体会是做完547 - 200 - 990 - 684这四道题并查集的合并—查询—冲突检测三板斧基本就固化了之后再遇到分组连接圈子这类关键词脑子里自动就会弹出模板。5.3 并查集在真实系统里的应用刷题时很多人会问这东西真的有人用吗——有而且不少。最典型的是社交网络中的好友关系管理判断两个用户是否在同一个圈子、是否需要推荐可能认识的人都可以抽象成动态连通性问题。另一个例子是数据库分库分表时的一致性哈希环维护当节点扩容或缩容时需要重新分配数据归属并查集可以用来快速合并相邻节点组。还有图像处理中的连通域标记比如OCR里把相邻像素组成一个字符块本质上就是二维网格的连通分量问题。所以别小看这道看似简单的省份数量它背后的模型是真实工程里的常客。6. 写在刷题流水账最后模板怎么练才能变成肌肉记忆6.1 2026年刷题季的稳定性建议我看到标题里的2026年估计你也是把这题排进了今年的刷题计划。关于刷题这件事我吃过不少亏最痛的领悟是不要只图刷过要图稳定AC。什么意思呢很多人第一次做这题看题解能看懂但过一个月回来写还是会卡在某个细节上。我的建议是给自己立一个模板清单DFS模板visited数组 递归遍历 进入即标记BFS模板Deque队列 poll后遍历邻接点 入队即标记并查集模板parent、rank、find、union、count五个组件缺一不可。每个模板至少默写三遍。不是照着题解默写而是盖住代码从头写写完再对照。第一遍会卡、第二遍勉强、第三遍基本顺了。这一步做扎实了比刷十道新题都有用。6.2 调试技巧如果你在写这题时答案不对先别急着怀疑并查集逻辑按下面顺序排查打印visited数组确认每次新省份都是从没访问过的城市开始的打印并查集的parent数组合并后确认根节点是否符合预期检查主循环是否只处理了i j的上三角别错写成j 0导致重复合并如果用的是DFS确认递归入口是否已经把起点visited[i] true否则可能从别的城市又搜回来。我自己在本地测试时习惯用最小的例子比如isConnected [[1]]应该返回1[[1,0],[0,1]]应该返回2。跑通这些再跑复杂示例定位问题会快得多。6.3 最后的个人体会回到这道题本身。它看起来简单但它的价值恰恰在于把图论里的连通分量概念、DFS/BFS/并查集三个核心算法串在了一起。如果你能不看题解独立写出并查集版本并且能解释清楚为什么路径压缩之后效率高、为什么对称矩阵只需要遍历一半那这道题才算真正吃透了。我个人复习时会再看一眼自己写的注释很多灵感都是从这些笨注释里反思出来的。比如我在并查集模板顶部会写一行count 是当前连通分量的数量union 成功一次就减一。下次看代码三秒钟就能恢复记忆。做算法题就是这样一题一题啃透模板一次次默写到了需要用的时候自然就能调出来。这篇就写到这希望你在 2026 年的刷题计划里每一道题都能刷得踏实。