Graph Valid Tree

261. 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.

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.

BFS

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges == null) {
return false;
}

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
}

for (int[] edge : edges) {
}

boolean[] visited = new boolean[n];

queue.offer(0);

while (!queue.isEmpty()) {
int node = queue.poll();

if (visited[node]) {
return false;
}

visited[node] = true;

for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
}
}
}

for (int i = 0; i < visited.length; i++) {
if (!visited[i]) {
return false;
}
}

return true;
}
}
``````

Union Find

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges == null) {
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 edges.length == n - 1;
}

private int find(int[] nums, int i) {
while (nums[i] != -1) {
i = nums[i];
}

return i;
}
}
``````

Hope this helps,
Michael