基于C 的网站开发源码,靖江网站定制,网站推广托管公司,山东住房与城乡建设部网站思路分析#xff1a;
首先定义变量 fa 用于记录并查集#xff0c;以及城市数量 n。定义了并查集的两个函数#xff0c;find 用于查找节点的根节点#xff0c;togother 用于合并两个节点所在的集合。在公共函数 findCircleNum 中#xff0c;初始化并查集#xff0c;然后遍…
思路分析
首先定义变量 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(vectorvectorint 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 数组记录每个城市是否已经被访问过vectorbool 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;}
};
