【LeetCode】323. Number of Connected Components in an Undirected Graph 解题报告 (C++)
2024-09-07 19:30:15
- 作者: 负雪明烛
- id: fuxuemingzhu
- 个人博客:http://fuxuemingzhu.cn/
题目地址:https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/
题目描述
Given n
nodes labeled from 0
to n - 1
and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 1
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1]
is the same as [1, 0]
and thus will not appear together in edges.
题目大意
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。
解题方法
并查集
看到求联通分量的题,一般都可以用并查集。比如1101. The Earliest Moment When Everyone Become Friends。
只要把并查集背下来,这个题目基本直接写上去就好了。
C++代码如下:
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
map_ = vector<int>(n, 0);
components = n;
for (int i = 0; i < n; ++i) {
map_[i] = i;
}
for (vector<int>& edge : edges) {
uni(edge[0], edge[1]);
}
return components;
}
int find(int a) {
if (a == map_[a])
return a;
return find(map_[a]);
}
void uni(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb)
return;
map_[pa] = pb;
components --;
}
private:
vector<int> map_;
int components;
};
日期
2019 年 9 月 22 日 —— 熬夜废掉半条命
最新文章
- postgresql 设置只读用户
- html/css 钢琴黑白格布局
- Ubuntu 14.04 安装VMware 12
- Net分布式系统之二:CentOS系统搭建Nginx负载均衡
- 学习ASP.NET MVC(四)——我的第一个ASP.NET MVC 实体对象
- 【MySQL】MySQL server has gone away 怎么处理?
- Neither BindingResult nor plain target object for bean
- Python ->;>; 第一个Python程序
- 混合高斯模型和EM算法
- DWZ主从结构计算
- C++11并行编程-条件变量(condition_variable)详细说明
- ViewGroup可实现上下、各地跑马灯效果滚动
- 为jEasyUi的日期控件添加一个“清空”按钮----通过修改1.4的easyui.min.js
- AIR使用文件对象操作文件和目录
- error:com.mysql.jdbc.exceptions.jdbc4.MySQLIntegrityConstraintViolationException
- Docker(二):Dockerfile 使用介绍
- Web测试入门:Selenium+Chrome+Python+Mac OS
- Java基础之数组详解
- WPF设计の不规则窗体
- Oracle 表空间不足引起的问题及解决方法
热门文章
- springboot与数据访问之jdbc
- mysql—将字符型数字转成数值型数字
- LightningChart JS v.3.3.0全新版本现已发布!
- C#筛选项联动,联动筛选
- RocketMQ这样做,压测后性能提高30%
- Spark 广播变量和累加器
- 零基础学习java------day5------do....while循环、嵌套、方法(函数)
- STM32代码常见的坑
- Bash shell(六)-管道命令
- Linux:-e、-d、-f、-L、-r、-w、-x、-s、-h、