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.
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.
一刷
題解：
樹滿足的兩個條件：
- 無環(huán)
- 邊的數(shù)目 == n(點的數(shù)目)-1
用union and find來判斷是否存在環(huán)。
public class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize n isolated islands
int[] nums = new int[n];
Arrays.fill(nums, -1);
// perform union find
for(int i=0; i<edges.length; i++){//num of edges
int x = find(nums, edges[i][0]);
int y = find(nums, edges[i][1]);
// if two vertices happen to be in the same set
// then there's a cycle
if(x == y) return false;//there is a cycle
//union
nums[x] = y;
}
return edges.length == n-1;
}
private int find(int nums[], int i){
if(nums[i] == -1) return i;//alone
return find(nums, nums[i]);
}
}
二刷：
首先用union and find來確認(rèn)無環(huán), 如果1->2, 那么1劃到2這個集中丽柿，然后確認(rèn)邊的數(shù)目==點的數(shù)目-1
public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] nums = new int[n];
Arrays.fill(nums, -1);
//union and find
for(int[] edge : edges){
int x = find(nums, edge[0]);
int y = find(nums, edge[1]);
if(x == y) return false;
nums[x] = y;
}
return n == edges.length + 1;
}
private int find(int[] nums, int node){
if(nums[node] == -1) return node;
else return find(nums, nums[node]);
}
}
