本文共 4074 字，大约阅读时间需要 13 分钟。
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-provinces 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
城市之间的相连关系构成无向图，其中，城市是节点，城市的相连表示图的边，isConnected为邻接矩阵表示形式，省份总数为图的连通分量个数。
计算图的连通分量个数这类题目，可以采用深度优先搜索，广度优先搜索或并查集等方法实现。
遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。
对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。
计算连通分量数的另一个方法是使用并查集。初始时，每个城市都属于不同的连通分量。遍历矩阵isConnected，如果两个城市之间有相连关系，则它们属于同一个连通分量，对它们进行合并。
遍历矩阵 isConnected 的全部元素之后，计算连通分量的总数，即为省份的总数。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-provinces/solution/sheng-fen-shu-liang-by-leetcode-solution-eyk0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public: int findCircleNum(vector >& isConnected) { int n = isConnected.size(); vector visited(n, false); int ans = 0; for(int city = 0; city < n; city++) { if(visited[city] == false) { ans++; dfs(city, isConnected, visited); } } return ans; } void dfs(int city, vector >& isConnected, vector &visited) { visited[city] = true; int n = isConnected.size(); for(int neighbor = 0; neighbor < n; neighbor++) { if(visited[neighbor] == false and isConnected[city][neighbor] == 1) { dfs(neighbor, isConnected, visited); } } }}; class Solution { public: int findCircleNum(vector >& isConnected) { int n = isConnected.size(); vector visited(n, false); queue que; int ans = 0; for(int candi = 0; candi < n; candi++) { if(visited[candi] == false) { ans++; que.push(candi); visited[candi] = true; while(!que.empty()) { int city = que.front(); que.pop(); for(int neighbor = 0; neighbor < n; neighbor++) { if(visited[neighbor] == false and isConnected[city][neighbor] == 1) { que.push(neighbor); visited[neighbor] = true; } } } } } return ans; }}; class Solution { public: int findCircleNum(vector >& isConnected) { int n = isConnected.size(); //将树的根节点Id作为集合的Id vector father(n);//记录节点i的父结点 for(int i = 0; i < n; i++) { father[i] = i;//初始时父结点为自身 } int ans = n; for(int i = 0; i < n; i++) { for(int j = 1; j < n; j++) { if(isConnected[i][j] == 1) { if(merge(i, j, father) == true) { ans--;//合并成功 } } } } return ans; } int find(int x, vector & father) { int root = x; while(father[root] != root) { root = father[root];//查找节点x的根节点root } while(father[x] != x) { int temp = father[x]; father[x] = root;//将x到root路径上的结点的father更新为root x = temp; } return x;//即root } int merge(int x, int y, vector & father) { int father_x = find(x, father); int father_y = find(y, father); //找到节点x, y的根节点 if(father_x == father_y) { //本来就是一个集合 return false;//合并失败 } //当根节点不相同时，将x的根节点的父结点设为y的根结点 father[father_x] = father_y; return true;//合并成功 }};