[LintCode] 178 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.

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


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.


思路
满足一张图是一棵树的条件：
1：所有n点连通
2：有且仅有n - 1条边


解法一
BFS
要检测是否所有点都连通，我们用BFS从0点开始遍历所有连通的节点。如果遍历结束连通节点数正好就是题目给出的节点数n，那么这个图是全部连通的。
有n个节点的树，edge的数目一定正正好好是n - 1。所以如果edge < n - 1，说明不连通。如果edge > n - 1，说明有环。



Code

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        
        if (n == 0) {
            return false;
        }
        
        if (edges.length != n - 1) {
            return false;
        }
        
        ArrayList<Integer>[] adjList = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < edges.length; i++) {
            adjList[edges[i][0]].add(edges[i][1]);
            adjList[edges[i][1]].add(edges[i][0]);
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        HashSet<Integer> hash = new HashSet<Integer>();
        queue.add(0);
        hash.add(0);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                hash.add(node);
                for (int j = 0; j < adjList[node].size(); j++) {
                    if (!hash.contains(adjList[node].get(j))) {
                        queue.offer(adjList[node].get(j));
                    }
                }
            }
        }
        
        return hash.size() == n;
    }
}

解法二
Union Find
把全部的edges都union起来，看最后component是不是只剩一个。

public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
     
    class UF {
        private int[] id;
        private int numComponent;
        
        public UF(int n) {
            id = new int[n];
            numComponent = n;
            for (int i = 0; i < n; i++) {
                id[i] = i;
            }
        }
        
        public int find(int i) {
            while (i != id[i]) {
                id[i] = id[id[i]];
                i = id[i];
            }
            return i;
        }
        
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i != j) {
                numComponent--;
            }
            id[i] = j;
        }
        
        public int getComponent() {
            return numComponent;
        }
    }
    
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        
        if (edges.length != n - 1) {
            return false;
        }
        
        UF uf = new UF(n);
        
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        
        return uf.getComponent() == 1;
    }
}