# Graph Valid Tree

Medium

## Question

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.

Notice

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.

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.

Tags

`Depth First Search` Facebook Zenefits `Union Find` `Breadth First Search` Google

Related Problems

Medium Find the Connected Component in the Undirected Graph

## Analysis

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

DFS, BFS均可以解此题，有趣的是Union Find的解法。// TODO: Add DFS, BFS

This problem can be converted to finding a cycle in a graph. It can be solved by using DFS (Recursion) or BFS (Queue).

#### DFS / BFS

##### BFS

``````for(int neighbor : graph.get(node))
{
queue.offer(neighbor);
graph.get(neighbor).remove((Integer)node);
}
``````

``````for(int i: map.get(top)){
// only putting new node into the queue
if(!visited[i])
queue.offer(i);
}
``````

``````// check cycle
int top = queue.poll();
if(visited[top]) return false;
``````

``````// fully connected
for(boolean b: visited){
if(!b) return false;
}
``````
##### DFS

DFS 类似，只是在recursive放入parent和当前节点curr时，选择curr != parent才进行下一层hasCycle的递归，这样如果出现二次访问，就说明了有cycle。

## Solution

Union Find Solution

``````public class Solution {
class UnionFind {
// Implemented with array instead of HashMap for simplicity
int[] parent;

// Constructor
UnionFind (int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

public int find(int x) {
return compressed_find(x);
}

public int compressed_find(int x) {
int x_parent = parent[x];
while (x_parent != parent[x_parent]) {
x_parent = parent[x_parent];
}

int temp = -1;
int t_parent = parent[x];
while (t_parent != parent[t_parent]) {
temp = parent[t_parent];
parent[t_parent] = x_parent;
t_parent = temp;
}
return x_parent;
}
public void union(int x, int y) {
int x_parent = find(x);
int y_parent = find(y);
if (x_parent != y_parent) {
parent[x_parent] = y_parent;
}
}
}
/**
* @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) {
// Validation of |V| - 1 = |E|
if (n - 1 != edges.length || n == 0) {
return false;
}
UnionFind uf = new UnionFind(n);
for (int i = 0; i < edges.length; i++) {
if (uf.find(edges[i][0]) == uf.find(edges[i][1])) {
return false;
}
uf.union(edges[i][0], edges[i][1]);
}
return true;
}
}
``````

Simplified Union Find (0ms 100%)

``````class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;

int[] parent = new int[n];
Arrays.fill(parent, -1);

for (int[] edge : edges) {
int x = find(edge[0], parent);
int y = find(edge[1], parent);

if (x == y) return false;
parent[x] = y;
}

return true;
}

int find(int node, int[] parent) {
if (parent[node] == -1) return node;

return parent[node] = find(parent[node], parent);
}
}
``````

Union Find - with path compression and weighted (1ms, 74.31%)

``````class Solution {
public class UnionFind {
int[] parent;
int[] rank;
int count;

public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
count = n;
}

public int find (int p) {
int root = p;
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}

public void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return;
}
if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
rank[rootA] += rank[rootB];
} else {
parent[rootA] = rootB;
rank[rootB] += rank[rootA];
}
count--;
}

public int getCount() {
return count;
}
}
public boolean validTree(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge: edges) {
if (uf.find(edge[0]) == uf.find(edge[1])) {
return false;
}
uf.union(edge[0], edge[1]);
}
return uf.getCount() == 1;
}
}
``````

DFS Solution

``````public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}

for(int[] edge: edges){
}

boolean[] visited = new boolean[n];

if(!helper(0, -1, map, visited))
return false;

for(boolean b: visited){
if(!b)
return false;
}

return true;
}

public boolean helper(int curr, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
if(visited[curr])
return false;

visited[curr] = true;

for(int i: map.get(curr)){
if(i!=parent && !helper(i, curr, map, visited)){
return false;
}
}

return true;
}
``````

DFS - another one

``````public class Solution {
public boolean validTree(int n, int[][] edges) {

// initialize vertices
for (int i = 0; i < n; i++)

for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
}

boolean[] visited = new boolean[n];

// make sure there's no cycle
return false;

// make sure all vertices are connected
for (int i = 0; i < n; i++) {
if (!visited[i])
return false;
}

return true;
}

// check if an undirected graph has cycle started from vertex u
boolean hasCycle2(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
if (visited[u]) {
return true;
}

visited[u] = true;

// skip putting v into recursion again if v == parent
if(v != parent && hasCycle(adjList, v, visited, u)){
return true;
}
}

return false;
}

// check if an undirected graph has cycle started from vertex u
boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
visited[u] = true;

for (int i = 0; i < adjList.get(u).size(); i++) {

if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
return true;
}

return false;
}
}
``````

BFS Solution

``````public boolean validTree(int n, int[][] edges) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0; i<n; i++){
ArrayList<Integer> list = new ArrayList<Integer>();
map.put(i, list);
}

for(int[] edge: edges){
}

boolean[] visited = new boolean[n];

queue.offer(0);
while(!queue.isEmpty()){
int top = queue.poll();
if(visited[top])
return false;

visited[top]=true;

for(int i: map.get(top)){
// only putting new node into the queue
if(!visited[i])
queue.offer(i);
}
}

// fully connected
for(boolean b: visited){
if(!b)
return false;
}

return true;
}
``````

BFS - Another One

``````    // BFS, using queue
private boolean valid(int n, int[][] edges)
{
// build the graph using adjacent list
List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
for(int i = 0; i < n; i++)
for(int[] edge : edges)
{
}

// no cycle
boolean[] visited = new boolean[n];
Queue<Integer> queue = new ArrayDeque<Integer>();
while(!queue.isEmpty())
{
int node = queue.poll();
if(visited[node])
return false;
visited[node] = true;
for(int neighbor : graph.get(node))
{
queue.offer(neighbor);
graph.get(neighbor).remove((Integer)node);
}
}

// fully connected
for(boolean result : visited)
{
if(!result)
return false;
}

return true;
}
}
``````