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 inedges.
Understand the problem:
A classic graph search problem. The key is first to transform from the edge list to the adjecent list. The problem is equivalent to whether the graph exists a circle. We could solve the problem by using either DFS or BFS.
A DFS solution:
public class Solution {
public boolean validTree(int n, int[][] edges) {
// Create an adj list
List<List<Integer>> adjList = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<Integer>());
}
for (int[] edge : edges) {
adjList.get(edge[1]).add(edge[0]);
adjList.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[n];
if (!validTreeHelper(n, edges, 0, -1, visited, adjList)) {
return false;
}
// Check the islands
for (boolean v : visited) {
if (!v) {
return false;
}
}
return true;
}
private boolean validTreeHelper(int n, int[][] edges, int vertexId, int parentId,
boolean[] visited, List<List<Integer>> adjList) {
if (visited[vertexId]) {
return false;
}
visited[vertexId] = true;
List<Integer> neighbors = adjList.get(vertexId);
for (Integer neighbor : neighbors) {
if (neighbor != parentId && !validTreeHelper(n, edges, neighbor, vertexId, visited, adjList)) {
return false;
}
}
return true;
}
}
A BFS solution:
public class Solution {
public boolean validTree(int n, int[][] edges) {
// Create an adj list
List<List<Integer>> adjList = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<Integer>());
}
for (int[] edge : edges) {
adjList.get(edge[1]).add(edge[0]);
adjList.get(edge[0]).add(edge[1]);
}
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(0);
while (!queue.isEmpty()) {
int vertexId = queue.poll();
if (visited[vertexId]) {
return false;
}
visited[vertexId] = true;
for (int neighbor : adjList.get(vertexId)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
}
}
}
// Check the islands
for (boolean v : visited) {
if (!v) {
return false;
}
}
return true;
}
}
If a graph is valid binary tree, it must follow the two conditions:
1. num of edges = num of nodes - 1
2. There is only 1 CC
BFS Solution:
public class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
// write your code here
if (n == 0) {
return edges == null || edges.length == 0;
}
if (edges.length != n - 1) {
return false;
}
Set<Integer> visited = new HashSet<>();
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
// add nodes to the adjList
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
adjList.get(from).add(to);
adjList.get(to).add(from);
}
// start bfs from each node, if it's not visited
bfs(adjList, 0, visited);
return visited.size() == n;
}
private void bfs(List<List<Integer>> adjList, int root, Set<Integer> visited) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(root);
visited.add(root);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adjList.get(node)) {
if (visited.contains(neighbor)) {
continue;
}
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
}
Update on 1/11/2021: Union-Find
public class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
// write your code here
if (n == 0) {
return edges == null || edges.length == 0;
}
if (edges.length != n -1) {
return false;
}
// get number of cc
UF uf = new UF(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.getNumCC() == 1;
}
}
class UF {
private int n;
private int[] parents;
private int numCC;
public UF(int n) {
this.n = n;
parents = new int[n];
numCC = n;
for (int i = 0; i < n; i++) {
parents[i] = i;
}
}
public int find(int x) {
int root = x;
while (parents[root] != root) {
root = parents[root];
}
// path compression
while (x != root) {
int temp = parents[x];
parents[x] = root;
x = temp;
}
return root;
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parents[px] = py;
numCC--;
}
}
public int getNumCC() {
return numCC;
}
}
