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:

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

Example 2:

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

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

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;
    }
}