并查集的定义

  • 在计算机科学中,并查集(英文:Disjoint-set data structure,直译为不交集数据结构)是一种数据结构,用于处理一些不交集(Disjoint sets,一系列没有重复元素的集合)的合并及查询问题。 并查集支持如下操作: 查询:查询某个元素属于哪个集合,通常是返回集合内的一个“代表元素”。
  • 简单的来说:并查集支持如下操作
    • 查询:查询两个元素是否在同一个集合中
    • 合并:合并两个集合
    • 添加:添加一个集合(不常用)
  • 满足上面的操作的数据结构都可以称为 并查集
  • image.png 并查集维护的集合都是一颗树,每个结点都指向它们的父结点,如果两个结点在同一颗树上,那么它们的祖先一定相同。

路径压缩优化

  • 不优化时我们查找 下图 4 这个结点的祖先(根),查找两次,显然第二次还是得从 最低层开始向上层跳跃。这样无非浪费时间,在第一次查询结束的时候我们就可以把沿路的结点的父结点更新成祖先结点,在下一次查找的时候,可以用几乎O(1)的时间查找出某个点的祖先。

    • image.png
  • 优化后,第二次查找后就能够很快的得出 4 结点的祖先结点。

    • image.png

并查集的操作

  • 变量介绍

    • p[i] -> 表示 i 这个元素的父结点是谁,也可以理解成 i 属于哪个集合。
  • 定义并查集

    • 		const int N = 1e5 + 5; // 根据题目数据范围定义
      		int p[N]; // 这里只定义一个 p数组用来保存集合关系,在不同的题中会保存一些额外的信息。
      		void init() {
      			for (int i = 0; i <= N; ++ i) p[i] = i; // 让每个元素自己为一个集合
      		}
      
  • 查找某一点属于哪个集合

    • 以查找结点4的祖先结点为例子
    • image.png
    • 	int find(int x) {
      		if (p[x] != x) p[x] = find(p[x]); // 这里有个路径压缩,将路径上的每个结点的父结点更新成查到的祖先结点
      		return p[x];
      	}
      
  • 合并两个集合

    • 也就是把两个集合的其中一个根结点的父结点等于另一个根结点
    • image.png
    • 	void merge(int a, int b) {
      		int fa = find(a), fb = find(b);
      		if (fa == fb) return;
      		p[fa] = fb; 
      	}
      

并查集维护额外信息

  1. 一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。现在要进行 m 个操作,操作共有两种:M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中

    • 这个题是一个并查集模板题,和上面的模板一样
    • 题目链接:合并集合
    • 	#include <iostream>
      	#include <algorithm>
      	#include <string>
      	using namespace std;
      
      	const int N = 1e5 + 5;
      	int p[N];
      
      	int find(int x) {
      	    return p[x] == x ? x:p[x] = find(p[x]);
      	}
      
      	int main() {
      	    int n, m;
      	    cin >> n >> m;
      	    for (int i = 1; i <= n; ++ i) p[i] = i;
      
      	    while (m --) {
      	        string op;
      	        int a, b;
      	        cin >> op;
      
      	        cin >> a >> b;
      
      	        if (op == "M") {
      	            p[find(a)] = find(b);
      	        } else if (op == "Q") {
      	            cout << (find(a) == find(b)?"Yes":"No") << endl;
      	        }
      	    }
      
      	    return 0;
      	}
      
  2. 给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。现在要进行 m 个操作,操作共有三种:C a b,在点 a 和点之间连一条边,a 和 b 可能相等;Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b 可能相等;Q2 a,询问点 a 所在连通块中点的数量;

    • 题目链接:连通块中点的数量
    • 根据题目我们可以知道我们需要额外维护的信息是每个集合中点的个数。
    • cnt[i] -> 表示以 i 为祖先的集合中元素的个数
    • 	            #include <iostream>
            #include <algorithm>
            #include <string>
            using namespace std;
      
            const int N = 1e5 + 5;
            int p[N], cnt[N];
      
            int find(int x) {
                return p[x] == x? x:p[x]=find(p[x]);
            }
      
            int main() {
                int n, m;
                cin >> n >> m;
                // 初始化,每个一开始自己是一个集合,该集合自由它自己
                for (int i = 1; i <= n; ++ i) p[i] = i, cnt[i] = 1;
      
                while(m --) {
                    string op;
                    cin >> op;
                    int a,b;
                    if (op == "C") {
                        cin >> a >> b;
                        int fa = find(a), fb = find(b);
                        if (fa == fb) continue;
                        p[fa] = fb;
                        cnt[fb] += cnt[fa]; // 合并集合的时候将,点相加,之后的cnt[fa] 就没有用了,因为路径压缩了
                    } else if (op == "Q1") {
                        cin >> a >> b;
      
                            cout << (find(a) == find(b)?"Yes":"No") << endl;
      
                    } else if (op == "Q2") {
                        cin >> a;
                        cout << cnt[p[a]] << endl; // 直接输出也是因为路径压缩了。
                    }
                }
            }
      
  3. 动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B 吃 C,C 吃 A。现有 N 个动物,以 1∼N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述:第一种说法是 1 X Y,表示 X 和 Y 是同类。第二种说法是 2 X Y,表示 X 吃 Y。此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。当前的话与前面的某些真的话冲突,就是假话;当前的话中 X 或 Y 比 N 大,就是假话;当前的话表示 X 吃 X,就是假话。你的任务是根据给定的 N 和 K 句话,输出假话的总数。

    • 题目链接:食物链
    • 这个题目中,我们知道有三种关系
      • A -> B -> C -> A
      • image.png
    • 我们如何判断这三种动物的关系呢?
      • 我们可以维护子结点到根结点的距离。d[i] -> i 这个结点到根结点的距离
      • d[i] % 3 = 0 -> 与根结点是同类
      • d[i] % 3 = 1 -> 被根结点吃
      • d[i] % 3 = 2 -> 吃根结点
      • 通过上这种距离到类型的映射我们可以得出任意两点的关系
      • image.png
    • 解决了动物关系的表示,我们就可以进行题接,接下来具体的看代码注释
      • 	#include <iostream>
        	#include <algorithm>
        	using namespace std;
        
        	const int N = 5e5 + 5;
        	int p[N], d[N];
        
        	int find(int x) {
        	    if (p[x] != x) {
        	        int t = find(p[x]); // 要在路径压缩前修改距离根结点的距离, 因为是递归回溯后就已经计算距离根最近结点的距离
        	        d[x] += d[p[x]]; // 加上它的父结点,路径未压缩前,它的父结点就是根结点
        	        p[x] = t;   // 压缩路径,将父结点改成该集合的根结点
        	    }
        	    return p[x];
        	}
        
        	int main() {
        	    int n, k;
        	    cin >> n >> k;
        
        	    for (int i = 1; i <= n; ++ i) p[i] = i;
        
        	    int res = 0;
        
        	    while (k --) {
        	        int op, x, y;
        	        cin >> op >> x >> y;
        	        if (x > n || y > n)  res ++; // 如果超过 n 则,说明是假话
        	        else if (op == 2 && x == y) res ++; // 
        	        else {
        	            int fx = find(x), fy = find(y);
        	            if (op == 1) { // xy 是同类
        	                if (fx == fy && (d[x] - d[y]) % 3 != 0) res ++; // 如果是同类,d[x] % 3 == d[y] % 3
        	                else if (fx != fy) {    // 如果不属于一个集合
        	                    p[fx] = fy;         // 将它们合并到一个集合种
        	                    d[fx] = d[y] - d[x];    // 因为 x y 是同类 所以 fx 所在集合 和 fy 所在集合合并时,必须保证 x y 同类关系不改变,d[fx] = (d[y] - d[x]);
        	                }
        	            } else {
        	                if (fx == fy && (d[x] - d[y] - 1) % 3 != 0) res ++; // 因为x吃y,所以必然d[x] % 3 - 1 == d[y] % 3;
        	                else if (fx != fy) { // 如果不在一个集合中, 将两个集合合并
        	                    p[fx] = fy;     
        	                    d[fx] = d[y] - d[x] + 1;    // 新连接边要保证 x y 的关系不改变
        	                }
        	            }
        	        }
        	    }
        	    cout << res << endl;
        	    return 0;
        	}
        
      • d[fx] = d[y] - d[x],d[fx] = d[y] - d[x] + 1 -> 为何会这样算呢,看下图
        • image.png