261. Graph Valid Tree

题目：

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.

链接： http://leetcode.com/problems/graph-valid-tree/

题解：

验证输入数组是否能组成一个树。看了一些资料，这属于并查集的问题。首先我们明确一下满足要求的解的条件:

题目给定了n个node，则假如能组成一棵树，则这棵树的edge数目为n - 1，所以我们一开始要判断edges.length == n - 1
不可以有环路，即这个无向图必须是acyclic的，所有的edges最后也只能组成一个connected components

在判断完edges.length == n - 1后，我们可以想到使用Union-Find中的Quick-Find。先构造一个长为节点数n的数组id，初始化数组每个元素与他们的index相等。接下来遍历无向图的edges矩阵，假如edges[i][0]和edges[i][1]已经联通，则这个图存在环，我们返回false，否则我们把这两个元素联通起来 - 遍历id数组，将其中所有值为pid的元素值更新为qid。数组遍历结束之后返回true。 Quadratic time还是非常巨大，所以我们还可以继续对这个方法进行优化，接下来的就是Weighted Quick Union + Path Compression了，留给二刷，继续前进。收获是接触到了并查集的概念，很高兴。

Time Complexity - O(n²)， Space Complexity - O(n)

public class Solution {
    public boolean validTree(int n, int[][] edges) {        // dynamic connectivity
        if(n < 0 || edges == null || edges.length != n - 1)
            return false;
        int[] id = new int[n];
        for(int i = 0; i < id.length; i++) {
            id[i] = i;
        }
        
        for(int i = 0; i < edges.length; i++) {
            if(!connected(id, edges[i][0], edges[i][1])) {
                union(id, edges[i][0], edges[i][1]);
            } else {
                return false;
            }
        }
        return true;
    }
    
    private boolean connected(int[] id, int p, int q) {
        return id[p] == id[q];
    }
    
    private void union(int[] id, int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for(int i = 0; i < id.length; i++) {
            if(id[i] == pid) {
                id[i] = qid;
            }
        }
    }
}

二刷:

首先检测边界条件，是否edges.length == n - 1。其次转化为无向图检测环路，我们可以使用Union-Find来做。

下面是Weighted Quick Union + Path Compression，一如Sedgewick大神教授的。

Java:

public class Solution {
    private int[] id;
    private int[] sz;
    public boolean validTree(int n, int[][] edges) {
        if (n < 0 || edges == null || edges.length != n - 1) {
            return false;
        }
        id = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        for (int i = 0; i < edges.length; i++) {
            if (!isConnected(edges[i][0], edges[i][1])) {
                union(edges[i][0], edges[i][1]);
            } else {
                return false;
            }
        }
        return true;
    }
    
    private int getRoot(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
    
    private void union(int i, int j) {
        int rootI = getRoot(i);
        int rootJ = getRoot(j);
        if (rootI == rootJ) {
            return;
        }
        if (sz[rootI] < sz[rootJ]) {
            id[rootI] = rootJ;
            sz[rootJ] += sz[rootI];
        } else {
            id[rootJ] = rootI;
            sz[rootI] += sz[rootJ];
        }
    }
    
    private boolean isConnected(int i, int j) {
        return getRoot(i) == getRoot(j);
    }
}

Reference:

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://www.youtube.com/watch?v=4SZTsQO9d6k&index=3&list=PLe-ggMe31CTexoNYnMhbHaWhQ0dvcy43t

https://en.wikipedia.org/wiki/Tree_(data_structure)

http://segmentfault.com/a/1190000003791051

http://blog.csdn.net/dm_vincent/article/details/7655764

http://blog.csdn.net/pointbreak1/article/details/48796691

http://nb4799.neu.edu/wordpress/?p=1143

http://algorithmsandme.in/2014/06/graphs-detecting-cycle-in-undirected-graph/

http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf

https://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/UnionFind.pdf

https://leetcode.com/discuss/52610/8-10-lines-union-find-dfs-and-bfs

https://leetcode.com/discuss/52563/ac-java-union-find-solution

https://leetcode.com/discuss/58600/a-java-solution-with-dfs

https://leetcode.com/discuss/72645/compressed-weighted-quick-union-solution-in-java-2ms