# 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**](https://en.wikipedia.org/wiki/Tree_\(graph_theory\)):

> “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).

### Union Find 思路

初始化Union Find的father map，让每一个节点的初始parent指向自己（自己跟自己是一个Group）；在循环读取edge list时，查找两个节点的parent，如果相同，说明形成了环（Cycle），那么这便不符合树（Tree）的定义，反之，如果不相同，则将其中一个节点设为另一个的parent，继续循环。

此外还有需要注意的是对于vertex和edge的validation，`|E| = |V| - 1`，也就是要验证 `edges.length == n - 1`，如果该条件不满足，则Graph一定不是valid tree。

### DFS / BFS

把输入的edge list转化为adjacency list，便于基于vertex的搜索。

#### BFS

在于每次遍历邻接表时，对于node的neighbor，放入BFS的queue中之后，就把node本身从neighbor的邻接表中移除。

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

或者，只在neighbor没有被遍历过时才放入queue中：

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

这样，在遍历出队列时，如果遇到元素被二次访问就说明有cycle。

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

最后遍历visited\[]，确认每一个元素都被遍历到，才是valid tree（没有落单的节点）

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

#### DFS

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

## Solution

Union Find Solution

```java
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%)

```java
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%)

```java
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

```java
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){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    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

```java
public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList<Integer>());

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

        boolean[] visited = new boolean[n];

        // make sure there's no cycle
        if (hasCycle(adjList, 0, visited, -1))
            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;

        for(int v: adjList.get(u)){
            // 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++) {
            int v = adjList.get(u).get(i);

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

        return false;
    }
}
```

BFS Solution

```java
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){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];

    LinkedList<Integer> queue = new LinkedList<Integer>();
    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](https://leetcode.com/problems/graph-valid-tree/discuss/69078/AC-Java-solutions%3A-Union-Find-BFS-DFS)

```java
    // 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++)
            graph.add(new HashSet<Integer>());
        for(int[] edge : edges)
        {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // no cycle
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(0);
        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;
    }
}
```

## Reference

* [LeetCode Discuss: Java Union-Find solution](https://discuss.leetcode.com/topic/21712/ac-java-union-find-solution/14)
* [Program Creek: Graph Valid Tree (Java) DFS & BFS](http://www.programcreek.com/2014/05/graph-valid-tree-java/)
* [Princeton CS: Union Find](https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf)