并查集 订阅
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。 展开全文
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
信息
中文名
并查集
外文名
Union Find
用    途
计算机编码
并查集主要操作
初始化把每个点所在集合初始化为其自身。通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。查找查找元素所在的集合,即根节点。合并将两个元素所在的集合合并为一个集合。通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。
收起全文
精华内容
下载资源
问答
  • 并查集

    万次阅读 2020-06-08 11:39:45
    在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作: Find:确定元素属于哪一个...

    在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作:

    Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
    Union:将两个子集合并成同一个集合。
    由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于创建单元素集合。有了这些方法,许多经典的划分问题可以被解决。

    为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着,Find(x) 返回x所属集合的代表,而Union使用两个集合的代表作为参数。

    public class UF {
        private final int[] parent;
        private final int[] rank;
    
        public UF(int size) {
            rank = new int[size];
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                rank[i] = 1;
                parent[i] = i;
            }
        }
    
        private int find(int index) {
            if (index != parent[index]) {
                parent[index] = find(parent[index]);
            }
            return parent[index];
        }
    
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    
        public void union(int p, int q) {
            int pRoot = find(p), qRoot = find(q);
            if (pRoot == qRoot) return;
            if (rank[pRoot] > rank[qRoot]) {
                parent[qRoot] = pRoot;
            } else if (rank[pRoot] < rank[qRoot]) {
                parent[pRoot] = qRoot;
            } else {
                rank[qRoot]++;
                parent[pRoot] = qRoot;
            }
        }
    
        public static void main(String[] args) {
            UF uf = new UF(26);
    //        ["a==b","b!=c","c==a"]
            String[] pa = {"a==b", "b!=c", "c==a"};
            for (String s : pa) {
                if (s.charAt(1) == '=') {
                    uf.union(s.charAt(0) - 'a', s.charAt(3) - 'a');
                }
            }
    
            for (String s : pa) {
                if (s.charAt(1) == '!') {
                    if (uf.isConnected(s.charAt(0) - 'a', s.charAt(3) - 'a')) System.out.println(false);
                }
            }
            System.out.println(true);
        }
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,305
精华内容 24,522
关键字:

并查集