Graph Valid Tree

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.

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.

Note: 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.

Solution

一樣，遇到圖的問題，除了 BFS/DFS，還得想到 Union-Find。這題用 UF 解會非常簡單，但如果用 BFS/DFS 解，會相對複雜許多。核心思路在於，一個 edge 的兩端不能連到同個 root，如果連到同個 root，就代表有環，因此就不是 valid tree。

    public boolean validTree(int n, int[][] edges) {
        int[] nums = new int[n];
        Arrays.fill(nums, -1);

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

            if (x == y) {
                return false;
            }

            nums[y] = x;
        }

        return edges.length == n - 1;
    }

    public int find(int[] nums, int i) {
        if (nums[i] == -1) {
            return i;
        }
        return find(nums, nums[i]);
    }