261.Graph Valid Tree

1-Union Find

• Is Cyclic
• Is From only one tree?

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

1. 这些边是否构成环路，如果有环则不能构成树

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

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

• union将两个节点放入一个集合中

• find找到该节点所属的集合编号

• areConnected判断两个节点是否是一个集合

• count返回该并查集中有多少个独立的集合

具体并查集的原理，参见这篇文章。简单来讲，就是先构建一个数组，节点0到节点n-1，刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后，每次union操作时，我们把整个并查集中，所有和第一个节点所属集合号相同的节点的集合号，都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入，把所有边加入我们的并查集中，加的同时判断是否有环路。最后如果并查集中只有一个集合，则说明可以构建树。

注意

因为要判断是否会产生环路，union方法要返回一个boolean，如果两个节点本来就在一个集合中，就返回假，说明有环路

class Solution {
    public boolean validTree(int n, int[][] edges) {
        //Check if edge num satisfy
        if((n - 1) != edges.length)
            return false;

        int[] roots = new int[n];
        Arrays.fill(roots, -1);
        for(int i = 0; i < edges.length; i++){
            int root1 = find(roots, edges[i][0]);
            int root2 = find(roots, edges[i][1]);
            //Exist Circle
            if(root1 == root2)
                return false;
            else
                roots[root1] = root2;
        }
        return true;
    }

    public int find(int[] roots, int node){
        if(roots[node] == -1)
            return node;
        else{
            roots[node] = find(roots, roots[node]);
            return roots[node];
        }
    }
}

2-BFS

https://leetcode.com/problems/graph-valid-tree/discuss/69042

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // initialize adjacency list.
        for (int i = 0; i < edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(0);

        // do DFS from vertex 0, after one round DFS, if there is no loop and visited contains all the vertexs,
        // it is a tree.
        boolean res = helper(-1, 0, visited, graph);
        if (!res) return res;
        return visited.size() == n ? true : false;
    }

    public boolean helper(int parent, int vertex, Set<Integer> visited, List<List<Integer>> graph) {
        List<Integer> subs = graph.get(vertex);
        for (int v : subs) {
            // if v is vertex's parent, continue.
            if (v == parent) continue; 
            // if v is not vertex's parent, and v is visited. that presents there is a cycle in this graph.
            if(visited.contains(v)) return false;
            visited.add(v);
            boolean res = helper(vertex, v, visited, graph);
            if (!res) return false;
        }
        return true;
    }
}