脚本宝典收集整理的这篇文章主要介绍了[LeetCode] Graph Valid Tree [Union Find],脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Problem
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.
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.
Note
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Solution
public class Solution {
int[] parents;
public boolean validTree(int n, int[][] edges) {
if (n-1 != edges.length) {
return false;
}
parents = new int[n];
//initialize n nodes as each own parent
for (int i = 0; i < n; i++) {
parents[i] = i;
}
for (int i = 0; i < n-1; i++) {
if (find(edges[i][0]) == find(edges[i][1])) {
return false; //if two nodes on edge[i] have the same parent, this edge makes a circle causing it invalid
}
else union(edges[i][0], edges[i][1]); //else union the two nodes on edge[i]
}
return true;
}
public int find(int node) {
//find the very first parent node, which is when the parent is the node itself
if (parents[node] == node) {
return node;
}
//find parent recursively
return find(parents[node]);
}
public void union(int a, int b) {
int finda = parents[a], findb = parent[b];
//when node a and node b have different ancient parents, union them with the same parent
if (finda != findb) {
parents[finda] = findb;
}
}
}
Update 2018-10
class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n-1) return false;
int[] nums = new int[n];
Arrays.fill(nums, -1);
for (int i = 0; i < edges.length; i++) {
int x = find(nums, edges[i][0]);
int y = find(nums, edges[i][1]);
if (x == y) return false;
nums[x] = y;
}
return true;
}
private int find(int[] nums, int k) {
if (nums[k] == -1) return k;
else return find(nums, nums[k]);
}
}
以上是脚本宝典为你收集整理的[LeetCode] Graph Valid Tree [Union Find]全部内容,希望文章能够帮你解决[LeetCode] Graph Valid Tree [Union Find]所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。