并查集

1.概念

• 一个可以快速实现如下操作的数据结构
  1. 合并两个集合
  2. 询问两个元素是否处于一个集合中

2.原理

• 每个集合用一棵树表示，树根编号为集合编号。每个节点存储它的父节点，即p[x]中存储着x的父节点
• 路径压缩：在访问完每一个节点之后，就把这个节点所在路径上的所有节点都直接作为根节点的子节点

3.常见操作

1. 判断树根：if(p[x] == x)
2. 求x所在的集合编号：while(p[x] != x) x = p[x]
3. 合并集合：p[x]为x的集合编号，p[y]为y的集合编号，则p[x] = y

4.时间复杂度：近乎$O(1)$

模板题：AcWing.836 合并集合

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int[] p;
    //寻找x的根节点的编号,含路径压缩
    static int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        p = new int[N];
        for(int i = 1; i <= n; i++) p[i] = i;
        while(m-- > 0){
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[1]);
            int b = Integer.parseInt(s[2]);
            if(s[0].equals("M")){
                p[find(a)] = find(b);
            }else{
                if(find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

AcWing.836 连通块中点的数量

• 大体和模板题一致，需要多维护一个size数组，其中只有每个集合的根节点所对应的size内容有意义
• 合并集合的时候，需要把被合并的集合的所有节点数量加到合并完的大集合中

Java代码

import java.io.*;
public class Main{
    private static final int N = 100010;
    private static int[] p;
    private static int[] size;

    static int find(int x){
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        p = new int[N];
        size = new int[N];
        for(int i = 1; i <= n; i++){
            p[i] = i;
            size[i] = 1;
        }
        while(m-- > 0){
            String[] s2 = br.readLine().split(" ");
            if(s2[0].equals("C")){
                int a = find(Integer.parseInt(s2[1]));
                int b = find(Integer.parseInt(s2[2]));
                if(a == b) continue;
                size[b] += size[a];
                p[a] = b;
            }else if(s2[0].equals("Q1")){
                int a = find(Integer.parseInt(s2[1]));
                int b = find(Integer.parseInt(s2[2]));
                if(a == b) System.out.println("Yes");
                else System.out.println("No");
            }else{
                System.out.println(size[find(Integer.parseInt(s2[1]))]);
            }
        }
    }
}

AcWing.240 食物链

• 食物链是个圈，只要给出两句真话：A吃B，B吃C即可推出C吃A，所以可以通过合并集合来使ABC三者之间产生关系
• 维护一个距离数组d，但是数组d存储的值又不完全是距离，d中维护值的意义是数字mod3之后对于根节点的相对距离，这也就意味着只有mod3之后的值有意义，所以d[x]可以为负数
  • $d[x]$ mod 3 == 0：与根节点同类
  • $d[x]$ mod 3 == 1：可以吃根节点
  • $d[x]$ mod 3 == 2：可以被根节点吃
• 因为食物链的环形关系，所以所有节点都可以最终合并到同一个集合中，且都可以产生三种关系之一。
• 如何判断假话
  • 如果x > n 或 y > n
  • 前面是真话，且当前这句为假话：那么原来维护的集合中已经存在两个动物的关系，所以判断d数组中的数据是否符合以上三条，不符合则是假话；如果两个节点不在同一个集合中，则合并两个集合，更新d数组

Java代码

import java.io.*;
public class Main{
    private static final int N = 50010;
    private static int[] p;
    private static int[] d;

    static int find(int x){
        if(x != p[x]){
            // p[x] = find(p[x]) 这句不能这么写，因为p[x]会被改变，导致后续d[x]计算出错
            int t = find(p[x]);
            d[x] += d[p[x]];
            p[x] = t;
        }
        return p[x];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int res = 0;
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        p = new int[N];
        d = new int[N];
        for(int i = 1; i <= n; i++) p[i] = i;
        while(m-- > 0){
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int x = Integer.parseInt(s[1]);
            int y = Integer.parseInt(s[2]);
            if(x > n || y > n) res++;
            else{
                //find之后，x，y都已经是根节点的直接子节点了，所以d[px]可以直接通过d[x],d[y]来计算
                int px = find(x);
                int py = find(y);
                if(a == 1){
                    if(px == py && (d[x]-d[y])%3 != 0){
                        res++;
                    }else if(px != py){
                        p[px] = py;
                        d[px] = d[y]-d[x];
                    }
                }else{
                    if(px == py && (d[x]-d[y]-1)%3 != 0){
                        res++;
                    }else if(px != py){
                        p[px] = py;
                        d[px] = d[y]-d[x]+1;
                    }
                }
            }
        }
        System.out.print(res);
    }
}