力扣--并查集547.省份数量

思路分析：

• 首先定义变量 fa 用于记录并查集，以及城市数量 n。
• 定义了并查集的两个函数，find 用于查找节点的根节点，togother 用于合并两个节点所在的集合。
• 在公共函数 findCircleNum 中，初始化并查集，然后遍历 isConnected 数组，将相连的城市进行合并。
• 最后使用 visited 数组记录每个城市是否已经被访问过，然后统计省份的数量并返回。

class Solution {int fa[201]; // 并查集数组，用于记录节点的父节点int n; // 城市数量// 定义并查集的查找函数，用于查找节点 x 的根节点（即所属集合的代表节点）int find(int x) {// 如果节点 x 的父节点就是它自己，则返回 xif (fa[x] == x)return x;// 否则，递归地查找 x 的父节点，并返回结果elsereturn find(fa[x]);}// 定义并查集的合并函数，用于合并节点 x 和节点 y 所在的两个集合void togother(int x, int y) {// 将节点 x 所在集合的根节点设为节点 y 所在集合的根节点fa[find(x)] = find(y);}public:// 定义一个公共函数，用于计算省份的数量int findCircleNum(vector<vector<int>>& isConnected) {// 获取城市数量n = isConnected.size();// 初始化并查集，将每个节点的父节点设为它自己for (int i = 0; i < n; i++)fa[i] = i;// 遍历 isConnected 数组，将相连的城市进行合并for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (isConnected[i][j] == 1)togother(i, j);}}// 使用 visited 数组记录每个城市是否已经被访问过vector<bool> visited(n, false);int count = 0; // 记录省份的数量// 遍历每个城市，对于每个城市，如果其所在集合的根节点尚未被访问过，则将其标记为已访问，并增加省份数量for (int i = 0; i < n; i++) {if (visited[find(i)] == false) {count++;visited[find(i)] = true;}}// 返回省份的数量return count;}
};