Graph Valid Tree(Medium)

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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? Show More Hint 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.

解题思路：

时间 O(N^M) 空间 O(1)

判断输入的边是否能构成一个树，我们需要确定两件事：

1. 这些边是否构成环路，如果有环则不能构成树
2. 这些边是否能将所有节点连通，如果有不能连通的节点则不能构成树

因为不需要知道具体的树长什么样子，只要知道连通的关系，所以并查集相比深度优先搜索是更好的方法。我们定义一个并查集的数据结构，并提供标准的四个接口：

1. union 将两个节点放入一个集合中
2. find 找到该节点所属的集合编号
3. areConnected 判断两个节点是否是一个集合
4. count 返回该并查集中有多少个独立的集合

Java代码

public class UnionFind {

        int[] ids;
        int cnt;

        public UnionFind(int size){
            this.ids = new int[size];
            //初始化并查集，每个节点对应自己的集合号
            for(int i = 0; i < this.ids.length; i++){
                this.ids[i] = i;
            }
            this.cnt = size;
        }

        public boolean union(int m, int n){
            int src = find(m);
            int dst = find(n);
            //如果两个节点不在同一集合中，将两个集合合并为一个
            if(src != dst){
                for(int i = 0; i < ids.length; i++){
                    if(ids[i] == src){
                        ids[i] = dst;
                    }
                }
                // 合并完集合后，集合数减一
                cnt--;
                return true;
            } else {
                return false;
            }
        }

        public int find(int m){
            return ids[m];
        }

        public boolean areConnected(int m, int n){
            return find(m) == find(n);
        }

        public int count(){
            return cnt;
        }
    }


 public boolean validTree(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for(int i = 0; i < edges.length; i++){
        // 如果两个节点已经在同一集合中，说明新的边将产生环路
        if(!uf.union(edges[i][0], edges[i][1])){
            return false;
        }
    }
    return uf.count() == 1;
}