建站软件免费版下载,培训心得总结怎么写,SUPERW上海网站建设工作室,华为官方网站手机商城首页文章目录1. 题目2. 解题1. 题目
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表#xff08;每条边都是一对节点#xff09;#xff0c;请编写一个函数来计算无向图中连通分量的数目。
示例 1:
输入: n 5 和 edges [[0, 1], [1, 2], [3, 4]]0 3| |1…
文章目录1. 题目2. 解题1. 题目
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表每条边都是一对节点请编写一个函数来计算无向图中连通分量的数目。
示例 1:
输入: n 5 和 edges [[0, 1], [1, 2], [3, 4]]0 3| |1 --- 2 4 输出: 2示例 2:
输入: n 5 和 edges [[0, 1], [1, 2], [2, 3], [3, 4]]0 4| |1 --- 2 --- 3输出: 1注意:
你可以假设在 edges 中不会出现重复的边。
而且由于所以的边都是无向边[0, 1] 与 [1, 0] 相同所以它们不会同时在 edges 中出现。来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考并查集
class dsu
{
public:vectorint f;dsu(int n){f vectorint(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a);int fb find(b);f[fa] fb;}int find(int a){int origin a;while(a ! f[a])a f[a];return f[origin] a;}int countUni(){int count 0;for(int i 0; i f.size(); i){if(i find(i))count;}return count;}
};
class Solution {
public:int countComponents(int n, vectorvectorint edges) {dsu u(n);for(auto e : edges)u.merge(e[0],e[1]);return u.countUni();}
};32 ms 10.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
