Graph Valid Tree

https://leetcode.com/problems/graph-valid-tree/description/

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.

Thoughts

UF的另一个用途, 检测non-linear data structure是否有环. 遍历每一条边, 看边上的两个点是否已经在同一个set, 如果是代表他们之前间接连起来过, 再把它们连起来肯定会形成环, 所以返回false. 因为是检测树不是森林, 所以最后应该只有一个set.

Code

class Solution {
    class UnionFind {
        int[] father;
        int size;
        UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
            size = n;
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return;
            }
            father[x] = y;
            size--;
        }

        public int find(int x) {
            if (x == father[x]) {
                return x;
            }
            father[x] = find(father[x]);
            return father[x];
        }
    }

    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.size == 1;
    }
}

Analysis

时间复杂度O(N^2), N为结点数目.