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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

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) {

// n must be at least 1

if (n < 1) return false;

// create hashmap to store info of edges

Map<Integer, Set<Integer>> map = new HashMap<>();

for (int i = 0; i < n; i++) map.put(i, new HashSet<>());

for (int[] edge : edges) {

map.get(edge[0]).add(edge[1]);

map.get(edge[1]).add(edge[0]);

}

// bfs starts with node in label "0"

Set<Integer> set = new HashSet<>();

Queue<Integer> queue = new LinkedList<>();

queue.add(0);

while (!queue.isEmpty()) {

int top = queue.remove();

// if set already contains top, then the graph has cycle

// hence return false

if (set.contains(top)) return false;

for (int node : map.get(top)) {

queue.add(node);

// we should remove the edge: node -> top

// after adding a node into set to avoid duplicate

// since we already consider top -> node

map.get(node).remove(top);

}

set.add(top);

}

return set.size() == 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++) {

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;

// union

nums[x] = y;

}

return edges.length == n - 1;

}

int find(int nums[], int i) {

if (nums[i] == -1) return i;

return find(nums, nums[i]);

}

}