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 = 5andedges = [[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
Understand the problem:edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together inedges.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;
}
}
