首页 > 代码库 > Graph Valid Tree -- LeetCode
Graph Valid Tree -- LeetCode
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每个边两端点所在的集合。因为树中的点都是连在一起的,最后肯定会在一个集合。注意的是,如果有一条边,一旦将它添加到树中后就会构成一个环,那么这条边的两个端点一定之前已经被添加进了树中(两个点属于同一个集合),否则,每条新加的边,至少有一个端点是之前不存在于这棵树中的(两个点属于不同的集合)。
1 class Solution { 2 public: 3 int find(vector<int> &parent, int x) { 4 if (parent[x] == x) return x; 5 int pa = find(parent, parent[x]); 6 parent[parent[x]] = pa; 7 return pa; 8 } 9 void merge(vector<int> &parent, int x, int y) {10 int parentX = find(parent, x);11 int parentY = find(parent, y);12 if (parentX != parentY)13 parent[parentY] = parentX;14 }15 bool validTree(int n, vector<pair<int, int>>& edges) {16 vector<int> parent(n, 0);17 for (int i = 0; i < n; i++) parent[i] = i;18 for (int i = 0; i < edges.size(); i++) {19 if (find(parent, edges[i].first) == find(parent, edges[i].second))20 return false;21 merge(parent, edges[i].first, edges[i].second);22 }23 return n -1 == edges.size();24 }25 };
Graph Valid Tree -- LeetCode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。