Graph Valid Tree
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.
No cycle, Connected undirected graph.
Union found
public boolean validTree(int n, int[][] edges) {
if(n <= 1) return true;
int [] union = new int[n];
int unionNumber = n;
Arrays.fill(union, -1);
for(int []edge : edges){
if(edge[0] > edge[1]) swap(edge, 0, 1);
int e1 = edge[0], e2 = edge[1];
while(union[e1] != -1)
e1 = union[e1];
while(union[e2] != -1)
e2 = union[e2];
if(e1 == e2) return false;
union[e2] = e1;
unionNumber --;
}
return unionNumber == 1;
}
private void swap(int []nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}