并查集

面试常用，代码短

并查集本身的作用:

将两个集合合并，
询问两个元素是否在一个集合中

近乎O(1)

树的形式，来维护

每一个集合的编号就是树根节点的编号 p[x] 表示 x的父节点

每一个点，存取父节点是谁，

每一个元素属于那个集合，找父，一直递归

问题一：如何判断树根 if(p[x]==x)

问题二：如何求x的集合编号 while(p[x]!=x) x=p[x]; 时间复杂度较高

问题三：如何合并两个集合， px是x的集合编号，py是y的编号， p[x] = y; 把x直接插到y上

优化：一个点找到祖先后，直接路径上的点都直接指向根节点，这个优化叫路径优化

模板

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

题目

AcWing

836 合并集合
837 连通块中点的数量

Ac836 合并集合

描述

一共有n个数，编号是1~n，最开始每个数各自在一个集合中。

现在要进行m个操作，操作共有两种：

“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；

“Q a b”，询问编号为a和b的两个数是否在同一个集合中；

解答

import java.io.*;

public class Main {
    static final int N = 100010;
    static int[] p = new int[N];
    static int m;
    static int n;
    
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
		int n = Integer.parseInt(line[0]); // n个整数
		int m = Integer.parseInt(line[1]);// m个指令
        //一开始每个数都是一个集合
        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("No");
                }else{
                    System.out.println("Yes");
                }
                    
                
            }
            
        }
        
    }
    
}

Ac837 连通块中数的数量

描述

给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。

现在要进行m个操作，操作共有三种：

“C a b”，在点a和点b之间连一条边，a和b可能相等；

“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；

“Q2 a”，询问点a所在连通块中点的数量；

分析：多了统计数量这个操作

解答

import java.io.*;
public class Main {
	static final int N = 100010;
	static int[] p = new int[N];
	static int[] size = new int[N];
	static int m;
	static int n;
    
    public static int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    
    public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] line = br.readLine().split(" ");
		int n = Integer.parseInt(line[0]); // n个整数
		int m = Integer.parseInt(line[1]);// m个指令
        
        //初始化
        for(int i=1;i<=n;i++){
			p[i]=i;
			size[i] = 1;
        }
        
        while(m-->0){
			String[] s = br.readLine().split(" ");

			if(s[0].equals("C")){
            	int a = Integer.parseInt(s[1]);
				int b = Integer.parseInt(s[2]);
				a = find(a);
				b=find(b);
				if(a != b){
					p[a] = b;
					size[b] += size[a]; // a插到b下面
				}
            }else if(s[0].equals("Q1")){
				int a = Integer.parseInt(s[1]);
				int b = Integer.parseInt(s[2]);
				
				if(find(a)!=find(b)){
					System.out.println("No");
				}
				else{
					System.out.println("Yes");
				}
            }else{
                int a = Integer.parseInt(s[1]);
				System.out.println(size[find(a)]); 
            }
        }
    }
}