南京网站搜索排名,门户网站建设维护,wordpress悬浮工具,装饰公司资质等级目录 题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给我们一个二维数组#xff0c;表示城市之间的连通情况#xff0c;连在一起的城市为一个省份#xff0c;问我们一共有多少个省份。
这…目录 题目
示例
分析
代码 题目 示例 分析
给我们一个二维数组表示城市之间的连通情况连在一起的城市为一个省份问我们一共有多少个省份。
这是一道很经典很纯粹的并查集题目。按照我自己的话来说并查集就是给将相连的元素都设置一个共同的源头在本题中我们让相连的城市都有一个共同的源头那么最后我们统计一下所有城市一共有多少个不同的源头即可确定是有多少个城市了。
这代码就是很标准的并查集模板大家记住并且理解即可。
首先我们需要定义一个长度和城市数量一样的数组用来存放每个城市的源头。
并且需要将每个城市的源头初始化成自己。
接着遍历城市之间的连通情况。如果城市之间是连通的那么我们需要将他们联系在一起即把他们的源头改成同一个。
首先是先找出他们各自的源头再把其中一个的源头的源头改成对方的源头。其中找出各自源头这一步是不断寻找源头列表里对应位置如果一个城市的源头不是自己那么我们就接着找这个城市的源头的源头直到找到源头是自己的城市那么这座城市就是我们需要寻找的城市的最终源头。
这对应了代码中的find函数。
记录完所有城市的连通情况之后我们再看看所有城市一共有几个最终源头将最终源头的数量返回出去即可。
代码
class Solution {
public:int find(int c,vectorint city){ //寻源if(ccity[c]) return c; //自己就是源头,直接返回city[c]find(city[c],city); //接着往上寻找源头return city[c]; }void join(int i,int j,vectorint city){ //添加关系ifind(i,city);jfind(j,city);if(ij) return; //如果源头一样returncity[i]j; //源头不一样就添加为一样,这边改成city[j]i也是可以的}int findCircleNum(vectorvectorint isConnected) {vectorintcity(isConnected.size()); //用来记录每个城市的源头for(int i0;iisConnected.size();i) city[i]i; //初始化成每个城市都是自己的源头for(int i0;iisConnected.size();i){for(int j0;jisConnected.size();j){if(isConnected[i][j]1) join(i,j,city); //如果城市间是相连的,则添加关系为源头一致}}//统计所有城市一共有多少个源头unordered_setintres;for(int c:city){res.insert(find(c,city));}return res.size();}
};
