LeetCode 261. 以图判树（全部连通+边数=V-1）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），
请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1： 输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]] 输出: true示例 2: 输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] 输出: false 注意：你可以假定边列表 edges 中不会出现重复的边。 由于所有的边是无向边，边 [0,1] 和边 [1,0] 是相同的， 因此不会同时出现在边列表 edges 中。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/graph-valid-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

请参考：数据结构–并查集（Disjoint-Set）

• 采用并查集判断连通，还可以BFS、DFS

class dsu {vector<int> f; public:dsu(int n){f.resize(n);for(int i = 0; i < n; ++i)f[i] = i;}void merge(int a, int b){int fa = find(a), 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:bool validTree(int n, vector<vector<int>>& edges) {dsu u(n);for(auto& e : edges)u.merge(e[0], e[1]);return edges.size()+1==n && u.countUni()==1;} };

20 ms 10.7 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的LeetCode 261. 以图判树（全部连通+边数=V-1）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。