261. Graph Valid Tree

time: O(edges*nodes)

space: O(n)

// means there is a circle in this graph, so it's not a tree
if (x == y) return false; 

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // edge false case => edges.length != n - 1
        // union find to check node's parent, if the point (x, y) has the same root
        // it means there is a circle in this graph, so it's not a tree
        
        if (n < 1 || edges == null || edges.length != n - 1) return false;
        
        int roots[] = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = -1;
        }
        for (int pair[] : edges) {
            int x = find(roots, pair[0]);
            int y = find(roots, pair[1]);
            if (x == y) return false;
            roots[x] = y;
        }
        return true;
    }
    
    // find ⇒ 只要有父親,就會一路往上找, 直到找到 root, 最後找到底了, 就會回傳根節點
    private int find(int roots[], int i) {
        while(roots[i] != -1) {
            i = roots[i];
        }
        return i;
    }
}

with template

time: O(V*E)

space: O(V)

是不是一顆樹

1. 先檢查 edges.length == n-1, 邊數 == node 數 -1

2. union 失敗（parent 一樣）代表有環, 不是一棵樹,

class Solution {
    class UnionFind {
        int parent[];
        UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }
        boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                return true;
            }
            return false;
        }
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) {
            return false;
        }
        
        UnionFind uf = new UnionFind(n);
        
        for (int[] edge : edges) {
            if (!uf.union(edge[0], edge[1])) {
                return false;
            }
        }
        return true;
    }
}

or use count, if at last count == 1 and edges.length == n-1 也可以, 但不會提前終止

class Solution {
    class UnionFind {
        int parent[];
        int count = 0;
        UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
                count++;
            }
        }
        void union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                parent[x] = y;
                count--;
            }
        }
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n-1) {
            return false;
        }
        
        UnionFind uf = new UnionFind(n);
        
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        if (uf.count != 1) {
            return false;
        }
        return true;
    }
}