261. 以图判树

本文主要是介绍261. 以图判树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定从 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 中。

 

思路：让我们来判断其是否为一棵树，如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环。

采用并查集来做，如果需要合并的两个节点位于同一个集合内，那说明有环存在。

最后找一下并查集一共有多少个老大，如果只有一个老大的话，那么说明所有的节点都是连在一起的，就是树。

class Solution {
public://找老大int find_father(vector<int> &f, int i){while(i!=f[i]){i=f[i];}return i;}bool validTree(int n, vector<vector<int>>& edges) {vector<int>f(n);//f存上级父节点，当f[i]=i时，说明是这个集合的老大//初始化f，每个节点都是自己的老大for(int i=0; i<n; ++i){f[i]=i;}//合并节点for(auto x:edges){int p=find_father(f, x[0]);int q=find_father(f, x[1]);if(p==q) return false;f[p]=q;}//找一共有多少个老大unordered_set<int>s;for(int i=0; i<f.size(); ++i){s.insert(find_father(f, i));}return s.size()==1;}
};

 

这篇关于261. 以图判树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---