178.Graph Valid Tree

1.Description(Medium)

Givennnodes labeled from0ton - 1and a list ofundirectededges (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 areundirected,[0, 1]is the same as[1, 0]and thus will not appear together in edges.

Example

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

2.Code

http://www.jiuzhang.com/solutions/graph-valid-tree/

http://www.cnblogs.com/grandyang/p/5257919.html

这道题给了我们一个无向图，让我们来判断其是否为一棵树，我们知道如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以我们的焦点就变成了验证是否是连通图和是否含有环,即

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

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

Version 1：Union Find

我们定义一个并查集的数据结构，并提供标准的四个接口：

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

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

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

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

具体并查集的原理，参见http://blog.csdn.net/dm_vincent/article/details/7655764。简单来讲，就是先构建一个数组，节点0到节点n-1，刚开始都各自独立的属于自己的集合。这时集合的编号是节点号。然后，每次union操作时，我们把整个并查集中，所有和第一个节点所属集合号相同的节点的集合号，都改成第二个节点的集合号。这样就将一个集合的节点归属到同一个集合号下了。我们遍历一遍输入，把所有边加入我们的并查集中，加的同时判断是否有环路。最后如果并查集中只有一个集合，则说明可以构建树。因为要判断是否会产生环路，union方法要返回一个boolean，如果两个节点本来就在一个集合中，就返回假，说明有环路.

Version 2:BFS

public boolean validTree(int n, int[][] edges) {
        if (n == 0) {
            return false;
        }

        if (edges.length != n - 1) {
            return false;
        }

        //Initial and fill the adjacencylist
        List<ArrayList<Integer>> adjacencylist=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++){
            adjacencylist.add(new ArrayList<Integer>());
        }
        for(int i=0;i<edges.length;i++){
            int a=edges[i][0];
            int b=edges[i][1];
            adjacencylist.get(a).add(b);
            adjacencylist.get(b).add(a);
        }

        HashSet<Integer> set=new HashSet<Integer>();
        Queue<Integer> queue=new LinkedList<Integer>();
        queue.offer(0);
        set.add(0);

        while(!queue.isEmpty()){
            int current=queue.poll();
            for(int element : adjacencylist.get(current)){
                if(set.contains(element)){
                    continue; //注意这里是continue
                }
                else{
                    set.add(element);
                    queue.offer(element);
                }
            }            
        }
        return (set.size()==n);
    }

BFS 解法2：用一个visited数组

public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    for(int i=0; i<n; i++){
        ArrayList<Integer> list = new ArrayList<Integer>();
        map.put(i, list);
    }

    for(int[] edge: edges){
        map.get(edge[0]).add(edge[1]);
        map.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];

    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(0);
    while(!queue.isEmpty()){
        int top = queue.poll();
        if(visited[top])
            return false;

        visited[top]=true;

        for(int i: map.get(top)){
            if(!visited[i])
                queue.offer(i);
        }
    }

    for(boolean b: visited){
        if(!b)
            return false;
    }

    return true;
}

BFS解法3：每次遍历到一个点的邻接点a时，就把a从他的邻接表中去掉别的点就不会再遍历到了。

// BFS, using queue
private boolean valid(int n, int[][] edges) {
    // build the graph using adjacent list
    List<Set<Integer>> graph = new ArrayList<Set<Integer>>();   
    for(int i = 0; i < n; i++)
        graph.add(new HashSet<Integer>());
    for(int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // no cycle
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<Integer>();
    queue.add(0);
    while(!queue.isEmpty()) {
        int node = queue.poll();
        if(visited[node])
            return false;
        visited[node] = true;
        for(int neighbor : graph.get(node)) {
            queue.offer(neighbor);
            graph.get(neighbor).remove((Integer)node);
        }
    }

    // fully connected
    for(boolean result : visited){
        if(!result)
            return false;
    }

    return true;
}