专栏首页Michael阿明学习之路LeetCode 261. 以图判树(全部连通+边数=V-1)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • 搜索(4)

    mathor
  • 1072 开学寄语 (20 分)

    可爱见见
  • CodeForces 1143A The Doors

    ShenduCC
  • HDOJ-1711(kmp算法)

    Given two sequences of numbers : a[1], a[2], … , a[N], and b[1], b[2], … , b[M] ...

    dejavu1zz
  • 2015-偶数求和

    有一个长度为n(n<=100)的数列,该数列定义为从2开始的递增有序偶数,现在要求你按照顺序每m个数求出一个平均值,如果最后不足m个,则以实际数量求平均值。编程...

    用户2038589
  • Java实现图片的滤镜效果滤镜实现总结

    在移动端或者在web开发时处理图片都是一件麻烦的事儿。我调研过很多library,特别是在移动端处理图片时动不动都需要使用 C++ 或者 OpenCV。这对于 ...

    fengzhizi715
  • Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

    题意:有n个节目,每个节目有一个持续的天数,你一天只能看一个节目,问你这么多天最多能看几个节目

    ShenduCC

扫码关注云+社区

领取腾讯云代金券