# 0261. Graph Valid Tree

<https://leetcode.com/problems/graph-valid-tree>

## Description

You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer n and a list of `edges` where `edges[i] = [ai, bi]` indicates that there is an undirected edge between nodes `ai` and `bi` in the graph.

Return `true` *if the edges of the given graph make up a valid tree, and* `false` *otherwise*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/12/tree1-graph.jpg)

```
**Input:** n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
**Output:** true
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/12/tree2-graph.jpg)

```
**Input:** n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
**Output:** false
```

**Constraints:**

* `1 <= 2000 <= n`
* `0 <= edges.length <= 5000`
* `edges[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* There are no self-loops or repeated edges.

## ac1: Union-find

* UF template
* Valid Tree: 1) all connected, 2)edges + 1 = vertices, 3)no cycle. 1)&2) is easier, but still need to know how to detect cycle.

```java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int i = 0; i < edges.length; i++) {
            if (uf.connected(edges[i][0],edges[i][1])) return false; // A cycle
            uf.union(edges[i][0],edges[i][1]);
        }
        return edges.length == n - 1;
    }
}

class UF {
    int[] father;
    int count;
    public UF(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    public void union(int p, int q) {
        int pFather = find(p);
        int qFather = find(q);
        if (pFather != qFather) {
            father[pFather] = qFather;
            count--;
        }
    }
    public int find(int p) {
        while (p != father[p]) p = father[p];
        return p;
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find (q);
    }
}
```

## ac2: Graph + DFS

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

        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int[] edge : edges) {
            int v = edge[0], w = edge[1];
            adjList.get(v).add(w);
            adjList.get(w).add(v);
        }

        boolean[] visited = new boolean[adjList.size()];
        if (hasCycle(adjList, visited, 0, 0)) {
            return false;
        }

        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) return false;
        }

        return true;
    }

    private boolean hasCycle(List<List<Integer>> adjList, boolean[] visited, int curr, int parent) {
        visited[curr] = true;
        for (int v : adjList.get(curr)) {
            if (!visited[v]) {
                visited[v] = true;
                hasCycle(adjList, visited, v, curr);
            } else if (v != parent) {
                return true;
            }
        }
        return false;
    }
}
```