并查集

近似 O(1)的时间复杂度

并查集能解决什么问题？

• 如何合并两个集合
• 如何两个元素在不在同一个区间内

并查集原理？

用一棵树来存储整个集合，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]代表它的父节点

衍生出问题

1. 如何判断树根？if(p[x] == x)
2. 如何求 x 的编号？while(p[x] != x) x = p[x]
3. 如何合并两个集合，x 代表第一个集合，y 代表第二个集合？p[x] = y

如何优化？

每遍历一次，让这个节点直接指向根节点，即可将时间复杂度优化为 O(1);

模版应用

836. 合并集合

import java.util.*;
import java.io.*;
public class Main{
    private static int p[] = new int[100010]; //声明父节点;
    public static void main(String [] args) throws IOException {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        int m = in.nextInt();
        while(m -- != 0){
            String op = in.next();
            if(op.equals("M")){
                int a = in.nextInt();
                int b = in.nextInt();
                p[find(a)] = find(b);
            }else{
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }
        }
        log.flush();
        log.close();
    }
    //查找x节点的父亲
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

837. 连通块中点的数量

同时维护当前区间内，有多少个数量

import java.util.*;
import java.io.*;
public class Main{
    public static int p[] = new int[100010];
    public static int size[] = new int[100010];

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1 ; i <= n ; i ++){
            p[i] = i;
            size[i] = 1;
        }
        while(m -- != 0){
            String op = in.next();
            if(op.equals("C")){

                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b)) continue;
                size[find(b)] += size[find(a)];
                p[find(a)] = b;
            }else if(op.equals("Q1")){
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }else{
                int k = in.nextInt();
                log.write(size[find(k)] + "\n");
            }
        }
        log.flush();
        log.close();

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

240. 食物链

维护当前集合里面到根节点的距离

import java.io.*;
import java.util.*;
public class Main{
    public static int[] p,d; //p存储父节点 d存储距离
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 1];
        d = new int[n + 1];
        int ans = 0 ; //表示假话的个数
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        while(m -- != 0){
            int op = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            if(x > n || y > n){
                ans += 1;
                continue;
            }
            int px = find(x);
            int py = find(y);
            switch (op) {
                case 1 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        if ((d[x] - d[y])%3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x];
                        p[px] = py;
                    }
                    break;
                }
                case 2 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        //推导出的关系为 （d[x]-d[y]）%3 == 1 则认为x可以吃y
                        //写成（d[x]-d[y]-1）%3 == 0 可以避免余数是负数的问题
                        //也可以写成（d[x]-d[y]）%3 +3 == 1
                        //==正确 -> != 错误
                        if ((d[x] - d[y] - 1) % 3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x] + 1;
                        p[px] = py;
                    }
                    break;
                }
                default : System.out.print("--");
            }
        }
        log.write(ans + " ");
        log.flush();
        log.close();
    }
    public static int find(int x){
        if(x != p[x]){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
}