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

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

[分析]
应用Union Find算法的好例子，对Union Find算法不熟悉，可参看
http://blog.csdn.net/dm_vincent/article/details/7655764
http://blog.csdn.net/dm_vincent/article/details/7769159
个人觉得该博文阐述非常通俗易懂，第二个链接是博主举的几个应用例子。
对这题依次实现了不同优化程度的union find算法，从运行时间可看出优化是很有效果的。

第二部分代码是利用教材中的UnionFind算法实现，实现中包含路径压缩和按大小以及按秩(rank)求并思想，且仅需要一个数组s[],初始时s[i] = -1, 在合并过程中根的s[]值是该根所对应树的size的相反数，而非根节点的s[]指向其父节点。每次find一个节点p会将p到根上的所有节点的父节点均置为根，从而高效压缩路径。利用unionFind求解该题时，需要稍修改union，union函数返回值改为布尔类型，union时，若发现两个节点已在同一颗树中，即root相同，说明该条边会使得树中产生一个cycle，返回false，说明输入并非valid tree。全部边顺利union结束还不能说明输入是valid tree，验证union后有且仅有一个根方能确认输入是valid tree。
优化的union可以按大小也可以按高度合并，因为路径压缩过程会改变树的高度，所以其与按高度求并并不完全兼容，书中提到目前并不清楚这种情况下如何有效重新计算高度，答案是不去计算，就让每棵树存储的高度是估计的高度（rank），理论上证明按秩求并和按大小求并效率是一样的，且高度的更新不如大小更新频繁。

public class Solution {
    // http://blog.csdn.net/dm_vincent/article/details/7655764
    int count = 0;
    int[] id = null;
    int[] size = null;
    public boolean validTree(int n, int[][] edges) {
        initUnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            int p = edges[i][0], q = edges[i][1];
            if (find(p) == find(q))
                return false;
            union(p, q);
        }
        return count == 1 ? true : false;
    }
    public void initUnionFind(int n) {
        id = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
        count = n;
    }
    //version 4: weighted quick union with path compression, find & union, very close to O(1)
    public int find(int p) {
        while (p != id[p]) {
            id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }
    public void union(int p, int q) { //same with version 3
        int pRoot = find(p), qRoot = find(q);
        if (size[pRoot] < size[qRoot]) {
            id[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        } else {
            id[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }
        count--;
    }
    //version 3: weighted quick union, find & union, O(logn)
    public int find3(int p) { // same with version 2
        while (p != id[p]) p = id[p];
        return p;
    }
    public void union3(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        if (size[pRoot] < size[qRoot]) {
            id[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        } else {
            id[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        }
        count--;
    }
    // version 2: quick union, find & union, O(tree height)
    public int find2(int p) {
        while (p != id[p]) p = id[p];
        return p;
    }
    public void union2(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        id[pRoot] = qRoot;
        count--;
    }
    // version 1: quick find, find O(1), union O(n)
    public int find1(int p) {
        return id[p];
    }
    public void union1(int p, int q) {
        int pId = find(p), qId = find(q);// 特别注意进入循环先保存原始值，循环过程id[p]会被更改
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId)
                id[i] = qId;
        }
        count--;
    }
}

public boolean validTree(int n, int[][] edges) {
        initUnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            if (!union(edges[i][0], edges[i][1]))
                return false;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] < 0) {
                count++;
            }
        }
        return count == 1;
    }
    private int[] s;
    private int count;
    public void initUnionFind(int n) {
        s = new int[n];
        for (int i = 0; i < n; i++)
            s[i] = -1;
    }
    public int find(int p) {
        if (s[p] < 0)
            return p;
        else {
            s[p] = find(s[p]);
            return s[p];
        }
    }
    // union by rank
    public boolean union(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        if (pRoot == qRoot)
            return false;
        if (s[pRoot] < s[qRoot]) {
            s[qRoot] = pRoot;
        } else {
            if (s[pRoot] == s[qRoot])
                s[qRoot]--;
            s[pRoot] = qRoot;
        }
        return true;
    }
    // union by size
    public boolean union1(int p, int q) {
        int pRoot = find(p), qRoot = find(q);
        if (pRoot == qRoot)
            return false;
        if (s[pRoot] < s[qRoot]) {
            s[pRoot] += s[qRoot];
            s[qRoot] = pRoot;
        } else {
            s[qRoot] += s[pRoot];
            s[pRoot] = qRoot;
        }
        return true;
    }

评论

3 楼 likesky3 2015-09-21  

看了数据结构书得知并不是迭代和递归的区别，yb君的写法的效果是从p到根的路径上每个节点都将根设为父节点，而我的写法效果是从p到根路径上每隔一个节点重置爷爷节点为父节点，压缩力度没有书上标准写法大，当然标准写法会多些递归开销。

2 楼 likesky3 2015-09-03  

迭代和递归的区别吧~

1 楼 qb_2008 2015-09-02  

还有一种find写法：
int find(int p) {
  if (id[p] == p) {
    return p;
  }
  return id[p] = find(id[p]);
}