给定从 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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