Graph Valid Tree -- LeetCode
2024-08-27 17:55:25
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 check whether these edges make up a valid tree.
For example:
Given n = 5
and edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
, return true
.
Given n = 5
and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
, return false
.
思路:union find。
是一个树的条件有两个:无环,边数等于节点数减一。
检测无环可以用union find:枚举所有的边,检测并更新他们端点所属的集合。一开始所有的节点都属于各自的集合,然后merge每个边两端点所在的集合。因为树中的点都是连在一起的,最后肯定会在一个集合。注意的是,如果有一条边,一旦将它添加到树中后就会构成一个环,那么这条边的两个端点一定之前已经被添加进了树中(两个点属于同一个集合),否则,每条新加的边,至少有一个端点是之前不存在于这棵树中的(两个点属于不同的集合)。
class Solution {
public:
int find(vector<int> &parent, int x) {
if (parent[x] == x) return x;
int pa = find(parent, parent[x]);
parent[parent[x]] = pa;
return pa;
}
void merge(vector<int> &parent, int x, int y) {
int parentX = find(parent, x);
int parentY = find(parent, y);
if (parentX != parentY)
parent[parentY] = parentX;
}
bool validTree(int n, vector<pair<int, int>>& edges) {
vector<int> parent(n, );
for (int i = ; i < n; i++) parent[i] = i;
for (int i = ; i < edges.size(); i++) {
if (find(parent, edges[i].first) == find(parent, edges[i].second))
return false;
merge(parent, edges[i].first, edges[i].second);
}
return n - == edges.size();
}
};
最新文章
- 基于Caffe的Large Margin Softmax Loss的实现(上)
- 永远不要修改arguments对象
- BZOJ 1040: [ZJOI2008]骑士 基环加外向树
- Oracle 常用操作
- MySQL索引背后的数据结构及最左原则
- Linux 3.2中回写机制的变革
- 【转】傅盛:一家公司最大瓶颈就是CEO
- 动态规划——Longest Valid Parentheses
- Elasticsearch安装部署教程
- 《剑指Offer》第1题(Java实现):在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
- java调用本地播放器播放视频文件。调用本地播放器不能播放指定文件的说明。
- plugin-barcodescanner 报错
- [UWP 自定义控件]了解模板化控件(3):实现HeaderedContentControl
- Java 11 究竟比 8 快了多少?看看这个基准测试
- WorldWind源码剖析系列:代理助手类ProxyHelper
- json中把非json格式的字符串转换成json对象再转换成json字符串
- fastcgi c/c++ API 说明
- Scala:fold,foldLeft和foldRight区别与联系 reduce
- HTML5+CSS3从入门到精通随书光盘 ISO 镜像视频教程​
- linux下c,c++头文件的路径