西安网站快速优化,北京信息网招聘最新,智慧团建登录网站入口,潍坊建站公司文章目录 题目原题链接思路C代码 题目 原题链接 LCR 116. 省份数量 思路
利用并查集的思想#xff0c;将连接的诚实放在一个集合当中#xff0c;最后遍历并查集数组判断有几颗树
初始化一个并查集#xff1b;将连通的城市合并#xff1b;统计并查集中树的个数#xff1b… 文章目录 题目原题链接思路C代码 题目 原题链接 LCR 116. 省份数量 思路
利用并查集的思想将连接的诚实放在一个集合当中最后遍历并查集数组判断有几颗树
初始化一个并查集将连通的城市合并统计并查集中树的个数
C代码
class Solution
{
public:int findCircleNum(vectorvectorint isConnected) {// 初始化并查集vectorint ufs(isConnected.size(), -1); auto findRoot [ufs](int x){int parent x;while (ufs[parent] 0) parent ufs[parent];return parent;};for(int i 0; i isConnected.size(); i)for(int j 0; j isConnected[0].size(); j){// 是否连通if(isConnected[i][j] 1){int root1 findRoot(i);int root2 findRoot(j);// 合并if (root1 ! root2) {ufs[root1] ufs[root2];ufs[root2] root1; }}}// 统计并查集中集合的个数int n 0;for (const int e : ufs) {if (e 0)n;}return n;}
};
