并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。

查询元素所在的集合编号，直接返回 id 数组值， O(1) 的时间复杂度。

...
private int find ( int p ) {
    assert p >= && p < count ;
    return id [ p ] ;
}
...

合并元素 p 和元素 q 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 O(n) 复杂度。

...
public void unionElements ( int p, int q ) {
    int pID = find ( p ) ;
    int qID = find ( q ) ;
    if ( pID == qID )
        return ;
    for ( int i = ; i < count ; i ++ )
        if ( id [ i ] == pID )
            id [ i ] = qID ;
}
...

Java 实例代码

源码包下载： Download

UnionFind1.java 文件代码：

package yssmx.union ;

/**
 * 第一版union-Find
 */
public class UnionFind1 {
    // 我们的第一版Union-Find本质就是一个数组
    private int [ ] id ;
    // 数据个数
    private int count ;

    public UnionFind1 ( int n ) {
        count = n ;
        id = new int [ n ] ;
        // 初始化, 每一个id[i]指向自己, 没有合并的元素
        for ( int i = ; i < n ; i ++ )
            id [ i ] = i ;
    }

    // 查找过程, 查找元素p所对应的集合编号
    private int find ( int p ) {
        assert p >= && p < count ;
        return id [ p ] ;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(1)复杂度
    public boolean isConnected ( int p, int q ) {
        return find ( p ) == find ( q ) ;
    }

    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    public void unionElements ( int p, int q ) {

        int pID = find ( p ) ;
        int qID = find ( q ) ;

        if ( pID == qID )
            return ;

        // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
        for ( int i = ; i < count ; i ++ )
            if ( id [ i ] == pID )
                id [ i ] = qID ;
    }
}