参考《算法竞赛进阶指南》、AcWing题库

并查集

并查集 (Disjoint-Set) 是一种可以动态维护若干个不重叠的集合, 并支持合并与查询的数据结构。详细地说, 并查集包括如下两个基本操作:

Get, 查询一个元素属于哪一个集合。
Merge, 把两个集合合并成一个大集合。

为了具体实现并查集这种数据结构, 我们首先需要定义集合的表示方法。在并查集中, 我们采用 “代表元” 法, 即为每个集合选择一个固定的元素, 作为整个集合的 “代表”。

其次, 我们需要定义归属关系的表示方法。第一种思路是维护一个数组 $f$ , 用 $f[x]$ 保存元素 $x$ 所在集合的 “代表”。这种方法可以快速查询元素的归属集合, 但在合并时需要修改大量元素的 $f$ 值, 效率很低。第二种思路是使用一个树形结构存储每个集合, 树上的每个节点都是一个元素, 树根是集合的代表元素。整个并查集实际上是一个森林 (若干棵树)。我们仍然可以维护一个数组 $f a$ 来记录这个森林, 用 $f a[x]$ 保存 $x$ 的父节点。特别地, 令树根的 $f a$ 值为它自己。这样一来, 在合并两个集合时, 只需连接两个树根 (令其中一个树根为另一个树根的子节点, 即 $f a\left[\operatorname{root}_{1}\right]=\operatorname{root}_{2}$ )。不过在查询元素的归属时, 需要从该元素开始通过 $f a$ 存储的值不断递归访问父节点, 直至到达树根。为了提高查询效率, 并查集引入了路径压缩与按秩合并两种思想。

路径压缩与按秩合并

读者可能已经注意到, 第一种思路 (直接用数组 $f$ 保存代表) 的查询效率很高, 我们不妨考虑把两种思路进行结合。实际上, 我们只关心每个集合对应的 “树形结构” 的根节点是什么, 并不关心这棵树的具体形态一一这意味着下图中的两棵树是等价的:

因此, 我们可以在每次执行 Get 操作的同时, 把访问过的每个节点 (也就是所查询元素的全部祖先) 都直接指向树根, 即把上图中左边那棵树变成右边那棵。这种优化方法被称为路径压缩。采用路径压缩优化的并查集, 每次 Get 操作的均摊复杂度为 $O(\log N)$ 。

还有一种优化方法被称为按秩合并。所谓 “秩”, 一般有两种定义。有的资料把并查集中集合的 “秩” 定义为树的深度 (未路径压缩时)。有的资料把集合的 “秩” 定义为集合的大小。无论采取哪种定义, 我们都可以把集合的 “秩” 记录在 “代表元素”，也就是树根上。在合并时都把 “秩” 较小的树根作为 “秩” 较大的树根的子节点。

值得一提的是, 当 “秩” 定义为集合的大小时, “按秩合并” 也称为 “启发式合并”, 它是数据结构相关问题中一种重要的思想, 应用非常广泛, 不只局限于并查集中。启发式合并的原则是: 把 “小的结构” 合并到 “大的结构” 中, 并且只增加 “小的结构” 的查询代价。这样一来, 把所有结构全部合并起来, 增加的总代价不会超过 $N \log N$ 。故单独采用 “按秩合并” 优化的并查集, 每次 Get 操作的均摊复杂度也是 $O(\log N)$ 。

同时采用 “路径压缩” 和 “按秩合并” 优化的并查集, 每次 Get 操作的均推复杂度可以进一步降低到 $O(\alpha(N))$ , 其中 $\alpha(N)$ 为反阿克曼函数, 它是一个比 “对数函数” $\log N$ 增长还要慢的函数, 对于 $\forall N \leq 2^{2^{10^{10992}}}$ , 都有 $\alpha(N)<5$ , 故 $\alpha(N)$ 可近似为一个常数。著名计算机科学家 R.E. Tarjan 于 1975 年发表的论文中给出了证明。

在实际应用中, 我们一般只用路径压缩优化就足够了。接下来, 我们对并查集的具体代码实现作一下具体说明。

class UnionFind {
public: 
    vector<int> fa, size;
    int part;

    UnionFind(int n) {
        for (int i = 0; i < n; ++i) fa.push_back(i);
        size.resize(n, 1);
        part = n;
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    bool merge(int x, int y) {
        int rootx = find(x), rooty = find(y);
        if (rootx == rooty) return false;

        if (size[rootx] > size[rooty]) swap(rootx, rooty);
        fa[rootx] = rooty;
        size[rooty] += size[rootx];
        --part;
        return true;
    }

    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

并查集的存储

使用一个数组 $f a$ 保存父节点 (根的父节点设为自己)。

1	int fa[SIZE];

并查集的初始化

设有 $n$ 个元素，起初所有元素各自构成一个独立的集合，即有 $n$ 棵 1 个点的数。

1	for (int i = 1; i <= n; ++i) fa[i] = i;

并查集的 Get 操作

若 $x$ 是树根，则 $x$ 就是集合代表，否则递归访问 $fa[x]$ 直至根节点。

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]); // 路径压缩，fa 直接赋值为代表元素
}

并查集的 Merge 操作

合并元素 $x$ 和元素 $y$ 所在的集合，等价于让 $x$ 的树根作为 $y$ 的树根的子节点。

1
2
3

void merge(int x, int y) {
	fa[get(x)] = get(y);
}

237. 程序自动分析

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 $x_1,x_2,x_3,…$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i≠x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为： $x_1=x_2，x_2=x_3，x_3=x_4，x_1≠x_4$ ，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第 $1$ 行包含 $1$ 个正整数 $t$ ，表示需要判定的问题个数，注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第 $1$ 行包含 $1$ 个正整数 $n$ ，表示该问题中需要被满足的约束条件个数。

接下来 $n$ 行，每行包括 $3$ 个整数 $i,j,e$ ，描述 $1$ 个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 $e=1$ ，则该约束条件为 $x_i=x_j$ ；若 $e=0$ ，则该约束条件为 $x_i≠x_j$ 。

输出格式

输出文件包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串 YES 或者 NO，YES 表示输入中的第 $k$ 个问题判定为可以被满足，NO 表示不可被满足。

数据范围

$1 \le n \le 10^5$
$1 \le i,j \le 10^9$

输入样例：

输出样例：

1
2

NO
YES

算法分析

先满足所有 “相等” 类型的约束条件。容易发现, 如果把每个变量看作无向图中的一个节点, 每个 “相等” 的约束条件看作无向图中的一条边, 那么两个变量相等当且仅当它们连通。于是, 我们可以把变量分成若干个集合, 每个集合都对应无向图中的一个连通块。

有两种方法求出这些集合。第一种是建出上面提到的无向图, 执行深度优先遍历, 划分出无向图中的每个连通块。第二种是使用并查集动态维护。起初, 所有变量各自构成一个集合; 对于每条 “相等” 的约束条件, 合并它约束的两个变量所在的集合即可。最后, 扫描所有 “不等” 类型的约束条件。若存在一条 “不等” 的约束条件, 它约束的两个变量处于同一个集合内, 则不可能被满足。若不存在这样的“不等” 约束, 则全部条件可以被满足。

值得注意的是, 本题中变量 $x$ 的范围很大。我们可以首先使用 “离散化” 方法把变量 $x$ 的范围映射到 $1 \sim 2 n$ 之内, 再用上述算法解决。

从这道题目我们看到, 并查集能在一张无向图中维护节点之间的连通性, 这是它的基本用途之一。实际上, 并查集擅长动态维护许多具有传递性的关系。所谓传递性, 顾名思义, 就是指如果 $A$ 与 $B$ 有某种关系, $B$ 与 $C$ 有某种关系, 那么 $A$ 与 $C$ 也有某种确定的关系。本题中的 “等于”就是一种传递关系, 而 “不等于” 则显然不具有传递性。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100006;
int n, m, a[N*2], fa[N*2];
struct P {
	int i, j;
	bool e;
} p[N];

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

int find(int x) {
	return lower_bound(a + 1, a + m + 1, x) - a;
}

void cxzdfx() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].i >> p[i].j;
		cin >> p[i].e;
		a[2*i-1] = p[i].i;
		a[2*i] = p[i].j;
	}
	sort(a + 1, a + 2 * n + 1);
	m = unique(a + 1, a + 2 * n + 1) - (a + 1);
	for (int i = 1; i <= m; i++) fa[i] = i;
	for (int i = 1; i <= n; i++)
		if (p[i].e) fa[get(find(p[i].i))] = get(find(p[i].j));
	for (int i = 1; i <= n; i++)
		if (!p[i].e && get(find(p[i].i)) == get(find(p[i].j))) {
			puts("NO");
			return;
		}
	puts("YES");
}

int main() {
	int t;
	cin >> t;
	while (t--) cxzdfx();
	return 0;
}

Solution

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int fa[2 * N];
unordered_map<int, int> hm;

struct Query {
    int x, y, e;
}query[N];

int get(int x) { // 离散化
    if (hm.count(x) == 0) hm[x] = ++m;
    return hm[x];
}

int find(int x) {
    if (fa[x]  == x) return x;
    return fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int rootx = find(x), rooty = find(y);
    if (rootx == rooty) return false;
    fa[rootx] = rooty;
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        hm.clear();
        m = 0;
        
        cin >> n;
        
        for (int i = 1; i <= n; ++i) {
            int x, y, e;
            cin >> x >> y >> e;
            query[i] = {get(x), get(y), e};
        }
        
        for (int i = 1; i <= m; ++i) fa[i] = i; // m 是离散化后的范围，1 ~ m    
        
        for (int i = 1; i <= n; ++i) {
            if (query[i].e == 1) {
                merge(query[i].x, query[i].y);
            }
        }
        
        bool flag = true;
        for (int i = 1; i <= n; ++i) {
            if (query[i].e == 0) {
                int rootx = find(query[i].x), rooty = find(query[i].y);
                if (rootx == rooty) {
                    flag = false;
                    break;
                }
            }
        }
        
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

145. 超市

超市里有 $N$ 件商品，每件商品都有利润 $p_i$ 和过期时间 $d_i$ ，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式

输入包含多组测试用例。

每组测试用例，以输入整数 $N$ 开始，接下来输入 $N$ 对 $p_i$ 和 $d_i$ ，分别代表第 $i$ 件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式

对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围

$0 \le N \le 10000$ ,
$1 \le p_i,d_i \le 10000$
最多有 $14$ 组测试样例

输入样例：

4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10

输出样例：

1
2

80
185

算法分析

在二叉堆做法中, 我们把商品按照过期时间从前到后排序, 然后依次尝试用每个商品替换掉堆中利润较低的商品。

另一种显而易见的贪心策略则是, 优先考虑卖出利润大的商品, 并且对每个商品, 在它过期之前尽量晩卖出一一占用较晩的时间, 显然对其他商品具有 “决策包容性” 。

于是我们可以把商品按照利润从大到小排序, 并建立一个关于 “天数” 的并查集, 起初每一天各自构成一个集合。对于每个商品, 若它在 $d$ 天之后过期, 就在并查集中查询 $d$ 的树根 (记为 $r$ )。若 $r$ 大于 0 , 则把该商品安排在第 $r$ 天卖出, 合并 $r$ 与 $r-1$ (令 $r$ 为 $r-1$ 的子节点), 答案累加该商品的利润。

这个并查集实际上维护了一个数组中 “位置” 的占用情况。每个 “位置” 所在集合的代表就是从它开始往前数第一个空闲的位置 (包括它本身)。当一个 “位置” 被占用时（某一天安排了商品，就把该 “位置” 在并查集中指向它前一个 “位置”。利用并查集的路径压缩, 就可以快速找到最晩能卖出的时间 (从过期时间往前数第一个空闲的天数)。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10006;
int n, fa[N];
pair<int, int> p[N];

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

void Supermarket() {
	int d = 0, ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].first >> p[i].second;
		d = max(d, p[i].second);
	}
	for (int i = 0; i <= d; i++) fa[i] = i;
	sort(p + 1, p + n + 1);
	for (int i = n; i; i--) {
		int x = get(p[i].second);
		if (x) {
			ans += p[i].first;
			fa[x] = x - 1;
		}
	}
	cout << ans << endl;
}

int main() {
	while (cin >> n) Supermarket();
	return 0;
}

Solution

1250. 格子游戏（并查集判环）

Alice和Bob玩了一个古老的游戏：首先画一个 $n \times n$ 的点阵（下图 $n = 3$ ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为 $1$ ）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 $n$ 和 $m$ 。 $n$ 表示点阵的大小， $m$ 表示一共画了 $m$ 条线。

以后 $m$ 行，每行首先有两个数字 $(x, y)$ ，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 $D$ ，则是向下连一条边，如果是 $R$ 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 $m$ 步之后也没有结束，则输出一行“draw”。

数据范围

$1 \le n \le 200$ ，
$1 \le m \le 24000$

输入样例：

输出样例：

算法分析

并查集(典型并查集判断是否存在环的问题)

1、将每个坐标看成一个点值，为了方便计算，将所有的坐标横纵坐标都减1，第一个位置即(1,1)看成是0，(1,2)看成是1，依次类推，将所有的坐标横纵坐标都减1后，假设当前点是(x,y),则该点的映射值是a = (x * n + y)，
若向下画，则b = [(x + 1) * n + y],若向右画，则b = [x * n + y - 1]
2、枚举所有操作，通过并查集操作判断a和b是否在同一个集合，
- 若在同一个集合则标记此操作可以让格子形成环
- 若不在同一个集合，则需要将两个集合进行合并

并查集解决的是连通性（无向图联通分量）和传递性（家谱关系）问题，并且可以动态的维护。抛开格子不看，任意一个图中，增加一条边形成环当且仅当这条边连接的两点已经联通，于是可以将点分为若干个集合，每个集合对应图中的一个连通块。

Solution

#include <iostream>
using namespace std;

const int N = 40010;

int fa[N];

int n, m;

void init() {
    for (int i = 0; i < n * n; ++i) fa[i] = i;
}

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int rootx = find(x), rooty = find(y);
    if (rootx == rooty) return false;
    fa[rootx] = rooty;
    return true;
}

int getId(int x, int y) {
    return x * n + y;
}

int main() {
    cin >> n >> m;
    
    init();
    
    int ans = 0;
    
    for (int i = 1; i <= m; ++i) {
        int x, y;
        char d;
        cin >> x >> y >> d;
        --x, --y;
        int a = getId(x, y);
        int b;
        if (d == 'D') b = getId(x + 1, y);
        else b = getId(x, y + 1);
        if (!merge(a, b)) {
            ans = i;
            break;
        }
    }
    
    if (ans == 0) cout << "draw";
    else cout << ans;
}

1252. 搭配购买

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 $n$ 朵云，云朵被编号为 $1,2,…,n$ ，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 $1$ 行包含三个整数 $n，m，w$ ，表示有 $n$ 朵云， $m$ 个搭配，Joe有 $w$ 的钱。

第 $2 \sim n+1$ 行，每行两个整数 $c_i，d_i$ 表示 $i$ 朵云的价钱和价值。

第 $n+2 \sim n+1+m$ 行，每行两个整数 $u_i，v_i$ ，表示买 $u_i$ 就必须买 $v_i$ ，同理，如果买 $v_i$ 就必须买 $u_i$ 。

输出格式

一行，表示可以获得的最大价值。

数据范围

$1 \le n \le 10000$ ,
$0 \le m \le 5000$ ,
$1 \le w \le 10000$ ,
$1 \le c_i \le 5000$ ,
$1 \le d_i \le 100$ ,
$1 \le u_i,v_i \le n$

输入样例：

输出样例：

算法分析

把每一个连通块看做是一个物品，然后就变成了一个简单的 01 背包问题了。

在每个集合的根节点维护该集合的价钱和价值，即体积和重量。

Solution

#include <iostream>
using namespace std;

const int N = 1e4 + 10;


int n, m, vol;
int v[N], w[N];
int fa[N];
int f[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int rootx = find(x), rooty = find(y);
    
    if (rootx == rooty) return false;
    
    v[rooty] += v[rootx];
    w[rooty] += w[rootx];
    fa[rootx] = rooty;
    return true;
}

int main() {
    cin >> n >> m >> vol;
    
    for (int i = 1; i <= n; ++i) fa[i] = i;
    
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }
    
    for (int i = 1; i <= n; ++i) {
        if (fa[i] != i) continue; 
        for (int j = vol; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[vol];
}

“扩展域” 与 “边带权” 的并查集

并查集实际上是由若干棵树构成的森林, 我们可以在树中的每条边上记录一个权值, 即维护一个数组 $d$ , 用 $d[x]$ 保存节点 $x$ 到父节点 $f a[x]$ 之间的边权。

在每次路径压缩后, 每个访问过的节点都会直接指向树根, 如果我们同时更新这些节点的 $d$ 值, 就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。这就是所谓 “边带权” 的并查集。

238. 银河英雄传说 - AcWing题库

有一个划分为 $N$ 列的星际战场，各列依次编号为 $1,2,…,N$ 。

有 $N$ 艘战舰，也依次编号为 $1,2,…,N$ ，其中第 $i$ 号战舰处于第 $i$ 列。

有 $T$ 条指令，每条指令格式为以下两种之一：

M i j，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。
C i j，表示询问第 $i$ 号战舰与第 $j$ 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 条指令。

接下来 $T$ 行，每行一个指令，指令有两种形式：M i j 或 C i j。

其中 $M$ 和 $C$ 为大写字母表示指令类型， $i$ 和 $j$ 为整数，表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：

如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 $i$ 号战舰与第 $j$ 号战舰之间布置的战舰数目，如果第 $i$ 号战舰与第 $j$ 号战舰当前不在同一列上，则输出 $-1$ 。

数据范围

$N \le 30000 , T \le 500000$

输入样例：

输出样例：

1
2

-1
1

算法分析

一条 “链” 也是一棵树, 只不过是树的特殊形态。因此可以把每一列战舰看作一个集合, 用并查集维护。最初, $N$ 个战舰构成 $N$ 个独立的集合。

在没有路径压缩的情况下, $f a[x]$ 就表示排在第 $x$ 号战舰前面的那个战舰的编号。一个集合的代表就是位于最前边的战舰。另外, 让树上每条边带权值 1 , 这样树上两点之间的距离减 1 就是二者之间间隔的战舰数量。

在考虑路径压缩的情况下, 我们额外建立一个数组 $d, d[x]$ 记录战舰 $x$ 与 $f a[x]$ 之间的边的权值。在路径压缩把 $x$ 直接指向树根的同时, 我们把 $d[x]$ 更新为从 $x$ 到树根的路径上的所有边权之和。下面的代码对 Get 函数稍加修改, 即可实现对 $d$ 数组的维护:

// 边带权的并查集
int get(int x) {
	if (x == fa[x]) return x;
	int root = get(fa[x]);  // 递归计算集合代表
	d[x] += d[fa[x]];       // 维护d数组——对边权求和
	return fa[x] = root;    // 路径压缩 
}

当接收到一个 $\mathrm{C} \;x \;y$ 指令时, 分别执行 $\operatorname{get}(x)$ 和 $\operatorname{get}(y)$ 完成查询和路径压缩。若二者的返回值相同, 则说明 $x$ 和 $y$ 处于同一列中。因为 $x$ 和 $y$ 此时都己经指向树根, 所以 $d[x]$ 保存了位于 $x$ 之前的战舰数量, $d[y]$ 保存了位于 $y$ 之前的战舰数量。二者之差的绝对值再减 1 , 就是 $x$ 和 $y$ 之间间隔的战舰数量。

当接收到一个 $\mathrm{M} \;x \;y$ 指令时, 把 $x$ 的树根作为 $y$ 的树根的子节点, 连接的新边的权值应该设为合并之前集合 $y$ 的大小 (根据题意, 集合 $y$ 中的全部战舰都排在集合 $x$ 之前)。因此, 我们还需要一个 size 数组在每个树根上记录集合大小。下面这段对 Merge 函数稍加修改的代码实现了这条指令:

void merge(int x, int y) {
	x = get(x), y = get(y);
	fa[x] = y, d[x] = size[y];
	size[y] += size[x];
}

刚才我们在 “程序自动分析”一题中提到, 并查集擅长维护具有传递性的关系及其连通性。在某些问题中, “传递关系” 不止一种, 并且这些 “传递关系” 能够互相导出。此时可以使用 “扩展域” 或者 “边带权” 的并查集来解决。我们通过几道例题来详细说明。另外, 我们会在 Tarjan算法与有向图连通性一文中探讨 2-SAT 模型, 学习之后读者就会更加深刻地理解并查集能够处理的 “关系” 本质。

Solution

#include <iostream>
using namespace std;

const int N = 30010;

int fa[N], sz[N], d[N];

void init() {
    for (int i = 1; i <= 30000; ++i) {
        fa[i] = i;
        sz[i] = 1;
        d[i] = 0;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);
    d[x] += d[fa[x]];
    return fa[x] = root;
}

bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    
    d[x] = sz[y];
    sz[y] += sz[x];
    fa[x] = y;
    return true;
}

int main() {
    init();
    
    int T;
    cin >> T;
    
    while (T--) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'M') {
            merge(x, y);
        } else {
            int rootx = find(x), rooty = find(y);
            if (rootx == rooty) cout << max(abs(d[x] - d[y]) - 1, 0) << endl;
            else cout << -1 << endl;
        }
    }
}

239. 奇偶游戏

小 $A$ 和小 $B$ 在玩一个游戏。

首先，小 $A$ 写了一个由 $0$ 和 $1$ 组成的序列 $S$ ，长度为 $N$ 。

然后，小 $B$ 向小 $A$ 提出了 $M$ 个问题。

在每个问题中，小 $B$ 指定两个数 $l$ 和 $r$ ，小 $A$ 回答 $S[l \sim r]$ 中有奇数个 $1$ 还是偶数个 $1$ 。

机智的小 $B$ 发现小 $A$ 有可能在撒谎。

例如，小 $A$ 曾经回答过 $S[1 \sim 3]$ 中有奇数个 $1$ ， $S[4 \sim 6]$ 中有偶数个 $1$ ，现在又回答 $S[1 \sim 6]$ 中有偶数个 $1$ ，显然这是自相矛盾的。

请你帮助小 $B$ 检查这 $M$ 个答案，并指出在至少多少个回答之后可以确定小 $A$ 一定在撒谎。

即求出一个最小的 $k$ ，使得 $01$ 序列 $S$ 满足第 $1 \sim k$ 个回答，但不满足第 $1 \sim k+1$ 个回答。

输入格式

第一行包含一个整数 $N$ ，表示 $01$ 序列长度。

第二行包含一个整数 $M$ ，表示问题数量。

接下来 $M$ 行，每行包含一组问答：两个整数 $l$ 和 $r$ ，以及回答 even 或 odd，用以描述 $S[l \sim r]$ 中有偶数个 $1$ 还是奇数个 $1$ 。

输出格式

输出一个整数 $k$ ，表示 $01$ 序列满足第 $1 \sim k$ 个回答，但不满足第 $1 \sim k+1$ 个回答，如果 $01$ 序列满足所有回答，则输出问题总数量。

数据范围

$N \le 10^9 , M \le 5000$

输入样例：

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出样例：

算法分析

如果我们用 sum 数组表示序列 $S$ 的前缀和, 那么在每个回答中:

$S[l \sim r]$ 有偶数个 1 , 等价于 $\operatorname{sum}[l-1]$ 与 $\operatorname{sum}[r]$ 奇偶性相同。
$S[l \sim r]$ 有奇数个 1 , 等价于 $\operatorname{sum}[l-1]$ 与 $\operatorname{sum}[r]$ 奇偶性不同。

注意, 这里没有求出 sum 数组, 我们只是把 sum 看作变量。读者可以发现, 此时本题与本节中 “程序自动分析”一题非常类似一一都是给定若干个变量和关系, 判定这些关系可满足性的问题。不同点是本题的传递关系不止一种:

若 $x_{1}$ 与 $x_{2}$ 奇偶性相同, $x_{2}$ 与 $x_{3}$ 奇偶性也相同, 那么 $x_{1}$ 与 $x_{3}$ 奇偶性相同。这种情况与 “程序自动分析” 中的等于关系一样。
若 $x_{1}$ 与 $x_{2}$ 奇偶性相同, $x_{2}$ 与 $x_{3}$ 奇偶性不同, 那么 $x_{1}$ 与 $x_{3}$ 奇偶性不同。
若 $x_{1}$ 与 $x_{2}$ 奇偶性不同, $x_{2}$ 与 $x_{3}$ 奇偶性也不同, 那么 $x_{1}$ 与 $x_{3}$ 奇偶性相同。

另外, 序列长度 $N$ 很大, 但问题数 $M$ 较少, 可以先用离散化方法把每个问题的两个整数 $l-1$ 和 $r$ 缩小到等价的 $1 \sim 2 M$ 以内的范围:

struct { int l, r, ans; } query[10010];
int a[20010], fa[20010], d[20010], n, m, t;
void read_discrete() { // 读入、离散化
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		char str[5];
		scanf("%d%d%s", &query[i].l, &query[i].r, str);
		query[i].ans = (str[0] == 'o' ? 1 : 0);
		a[++t] = query[i].l - 1;
		a[++t] = query[i].r;
	}
	sort(a + 1, a + t + 1);
	n = unique(a + 1, a + t + 1) - a - 1;
}

解法一：“边带权”并查集

为了处理本题的多种传递关系, 第一种解决方案是使用 “边带权” 的并查集。边权 $d[x]$ 为 0 , 表示 $x$ 与 $f a[x]$ 奇偶性相同; 为 1 , 表示 $x$ 与 $f a[x]$ 奇偶性不同。在路径压缩时, 对 $x$ 到树根路径上的所有边权做异或(xor)运算, 即可得到 $x$ 与树根的奇偶性关系。

对于每个问题, 设在离散化后 $l-1$ 和 $r$ 的值分别是 $x$ 和 $y$ , 设 ans 表示该问题的回答 ( 0 代表偶数个, 1 代表奇数个)。

先检查 $x$ 和 $y$ 是否在同一个集合内 (奇偶关系是否已知)。 $\operatorname{get}(x) 、 \operatorname{get}(y)$ 都执行完成后, $d[x]$ xor $d[y]$ 即为 $x$ 和 $y$ 的奇偶性关系(如下图)。若 $d[x]$ xor $d[y] \neq a n s$ (该关系与回答矛盾), 则在该问题之后即可确定小 $\mathrm{A}$ 撒谎。

若 $x$ 和 $y$ 不在同一个集合内, 则合并两个集合。此时应该先通过 get 操作得到两个集合的树根 (设为 $p$ 和 $q$ ), 令 $p$ 为 $q$ 的子节点。如下图所示。已知 $d[x]$ 与 $d[y]$ 分别表示路径 $x \sim p$ 与 $y \sim q$ 之间所有边权的 “xor 和”, $p \sim q$ 之间的边权 $d[p]$ 是待求的值。显然, 路径 $x \sim y$ 由路径 $x \sim p, p \sim q$ 与 $q \sim y$ 组成, 因此 $x$ 与 $y$ 的奇偶性关系 ans $=d[x]$ xor $d[y]$ xor $d[p]$ 。进而推出新连接的边权 $d[p]=d[x]$ xor $d[y]$ xor ans.

“边带权” 并查集解法的主要代码片段：

int get(int x) {
	if (x == fa[x]) return x;
	int root = get(fa[x]);
	d[x] ^= d[fa[x]];
	return fa[x] = root;
}
int main() {
	read_discrete();
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
		// 求出l-1和r离散化之后的值
		int x = lower_bound(a + 1, a + n + 1, query[i].l - 1) - a;
		int y = lower_bound(a + 1, a + n + 1, query[i].r) - a;
		// 执行get函数，得到树根，并进行路径压缩
		int p = get(x), q = get(y);
		if (p == q) { // 已经在同一集合内
			if ((d[x] ^ d[y]) != query[i].ans) { // 矛盾，输出
				cout << i - 1 << endl;
				return 0;
			}
		}
		else { // 不在同一集合，合并
			fa[p] = q;
			d[p] = d[x] ^ d[y] ^ query[i].ans;
		}
	}
	cout << m << endl; // 没有矛盾
}

解法二：“扩展域” 并查集

第二种解决方案是使用 “扩展域” 的并查集。

把每个变量 $x$ 拆成两个节点 $x_{o d d}$ 和 $x_{\text {even, }}$ , 其中 $x_{o d d}$ 表示 $\operatorname{sum}[x]$ 是奇数， $x_{e v e n}$ 表示 $\operatorname{sum}[x]$ 是偶数。我们也经常把这两个节点称为 $x$ 的 “奇数域” 和 “偶数域” 。

对于每个问题, 设在离散化后 $l-1$ 和 $r$ 的值分别是 $x$ 和 $y$ , 设 ans 表示该问题的回答 ( 0 代表偶数个, 1 代表奇数个)。

若 ans $=0$ , 则合并 $x_{\text {odd }}$ 与 $y_{\text {odd }}, x_{\text {even }}$ 与 $y_{\text {even}}$ 。这表示 “ $x$ 为奇数” 与 “ $y$ 为奇数” 可以互相推出, “ $x$ 为偶数” 与 “ $y$ 为偶数” 也可以互相推出, 它们是等价的信息。
若 ans $=1$ , 则合并 $x_{\text {odd }}$ 与 $y_{\text {even }}, x_{\text {even }}$ 与 $y_{\text {odd}}$ 。这表示 “ $x$ 为奇数” “ $y$ 为偶数” 可以互相推出, “ $x$ 为偶数” 与 “ $y$ 为奇数” 也可以互相推出, 它们是等价的信息。

上述合并同时还维护了关系的传递性。试想, 在处理完 $(x, y, 0)$ 和 $(y, z, 1)$ 两个回答之后, $x$ 和 $z$ 之间的关系也就已知了, 如下图所示。这种做法就相当于在无向图上维护节点之间的连通情况, 只是扩展了多个域来应对多种传递关系。

在处理每个问题之前, 我们当然也要先检查是否存在矛盾。若两个变量 $x$ 和 $y$ 对应的 $x_{o d d}$ 和 $y_{o d d}$ 节点在同一集合内, 则已知二者奇偶性相同。若两个变量 $x$ 和 $y$ 对应的 $x_{o d d}$ 和 $y_{e v e n}$ 节点在同一集合内, 则已知二者奇偶性不同。

// POJ1733 扩展域并查集做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct { int l, r, ans; } query[10010];
int a[20010], fa[40010], n, m, t;
void read_discrete() { // 读入、离散化
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		char str[5];
		scanf("%d%d%s", &query[i].l, &query[i].r, str);
		query[i].ans = (str[0] == 'o' ? 1 : 0);
		a[++t] = query[i].l - 1;
		a[++t] = query[i].r;
	}
	sort(a + 1, a + t + 1);
	n = unique(a + 1, a + t + 1) - a - 1;
}
int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
int main() {
	read_discrete();
	for (int i = 1; i <= 2 * n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
		// 求出l-1和r离散化之后的值
		int x = lower_bound(a + 1, a + n + 1, query[i].l - 1) - a;
		int y = lower_bound(a + 1, a + n + 1, query[i].r) - a;
		int x_odd = x, x_even = x + n;
		int y_odd = y, y_even = y + n;
		if (query[i].ans == 0) { // 回答奇偶性相同
			if (get(x_odd) == get(y_even)) { // 与已知情况矛盾
				cout << i - 1 << endl;
				return 0;
			}
			fa[get(x_odd)] = get(y_odd); // 合并
			fa[get(x_even)] = get(y_even);
		}
		else { // 回答奇偶性不同
			if (get(x_odd) == get(y_odd)) { // 与已知情况矛盾
				cout << i - 1 << endl;
				return 0;
			}
			fa[get(x_odd)] = get(y_even); // 合并
			fa[get(x_even)] = get(y_odd);
		}
	}
	cout << m << endl; // 没有矛盾
}

Solution

边带权

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

const int N = 10010;

int n, m;
int fa[N], d[N];
unordered_map<int, int> hm;

int get(int x) { // 哈希表实现无序离散化
    if (hm.count(x) == 0) hm[x] = ++n;
    return hm[x];
}

void init() {
    for (int i = 1; i < N; ++i) {
        fa[i] = i;
        d[i] = 0;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    
    int root = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = root;
}

int main() {
    init();
    
    cin >> n >> m;
    n = 0;
    
    int ans = m;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        string op;
        cin >> l >> r >> op;
        int x = get(l - 1), y = get(r);
        
        int rootx = find(x), rooty = find(y);
        if (rootx == rooty) {
            int t = d[x] ^ d[y];
            if (op == "even" && t) {
                ans = i - 1;
                break;
            }
            if (op == "odd" && !t) {
                ans = i - 1;
                break;
            }
        } else {
            if (op == "even") d[rootx] = d[x] ^ d[y];
            if (op == "odd") d[rootx] = d[x] ^ d[y] ^ 1;
            fa[rootx] = rooty;
        }
    }
    cout << ans;
}

扩展域

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

const int N = 20010;

int n, m;
int fa[2 * N];
unordered_map<int, int> hm;

int get(int x) { // 哈希表实现无序离散化
    if (hm.count(x) == 0) hm[x] = ++n;
    return hm[x];
}

void init() {
    for (int i = 1; i < 2 * N; ++i) {
        fa[i] = i;
    }
}

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    init();
    
    cin >> n >> m;
    n = 0;
    
    int ans = m;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        string op;
        cin >> l >> r >> op;
        int x = get(l - 1), y = get(r);
        
        if (op == "even") {
            if (find(x + N) == find(y)) {
                ans = i - 1;
                break;
            } else {
                fa[find(x)] = find(y);
                fa[find(x + N)] = find(y + N);
            }
        } 
        if (op == "odd") {
            if (find(x) == find(y)) {
                ans = i - 1;
                break;
            } else {
                fa[find(x + N)] = find(y);
                fa[find(x)] = find(y + N);
            }
        }
    }
    cout << ans;
}

240. 食物链

动物王国中有三类动物 $A,B,C$ ，这三类动物的食物链构成了有趣的环形。

$A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。

现有 $N$ 个动物，以 $1 \sim 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$ 句话，输出假话的总数。

输入格式

第一行是两个整数 $N$ 和 $K$ ，以一个空格分隔。

以下 $K$ 行每行是三个正整数 $D，X，Y$ ，两数之间用一个空格隔开，其中 $D$ 表示说法的种类。

若 $D=1$ ，则表示 $X$ 和 $Y$ 是同类。

若 $D=2$ ，则表示 $X$ 吃 $Y$ 。

输出格式

只有一个整数，表示假话的数目。

数据范围

$1 \le N \le 50000$ ,
$0 \le K \le 100000$

输入样例：

输出样例：

算法分析

本题仍然可以用 “边带权” 或者 “扩展域” 的并查集解决。我们以 “扩展域” 并查集为例进行讲解。

把每个动物 $x$ 拆成三个节点, 同类域 $x_{\text {self }}$ 、捕食域 $x_{\text {eat }}$ 和天敌域 $x_{\text {enemy}}{ }$ 。

若一句话说 “ $x$ 与 $y$ 是同类”, 则说明 “ $x$ 的同类” 与 “ $y$ 的同类”一样, “ $x$ 捕食的物种” 与 “ $y$ 捕食的物种” 一样, “ $x$ 的天敌” 与 “ $y$ 的天敌”一样。此时, 我们合并 $x_{\text {self }}$ 与 $y_{\text {self }}, x_{\text {eat }}$ 与 $y_{\text {eat }}, x_{\text {enemy }}$ 与 $y_{\text {enemy}}$ 。

若一句话说 “ $x$ 吃 $y$ ”, 说明 “ $x$ 捕食的物种” 就是 “ $y$ 的同类”, “ $x$ 的同类” 都是 “ $y$ 的天敌”。。因为题目中告诉我们食物链是长度为 3 的环形, 所以 “ $x$ 的天敌”就是“ $y$ 捕食的物种” ( $x$ 吃 $y, y$ 吃 $z, z$ 就吃 $x$ )。此时,应合并 $x_{\text {eat }}$ 与 $y_{\text {self }}$ , $x_{\text {self }}$ 与 $y_{\text {enemy }}, x_{\text {enemy }}$ 与 $y_{\text {eat }}$ 。

在处理每句话之前, 都要检查这句话的真假。

有两种信息与 “ $x$ 与 $y$ 是同类” 矛盾:

$x_{\text {eat }}$ 与 $y_{\text {self }}$ 在同一集合, 说明 $x$ 吃 $y$ 。
$x_{\text {self }}$ 与 $y_{\text {eat }}$ 在同一集合, 说明 $y$ 吃 $x$ 。

有两种信息与 “ $x$ 吃 $y$ ” 矛盾:

$x_{\text {self }}$ 与 $y_{\text {self }}$ 在同一集合, 说明 $x$ 与 $y$ 是同类。
$x_{\text {self }}$ 与 $y_{\text {eat }}$ 在同一集合, 说明 $y$ 吃 $x$ 。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int fa[200000];
int n, m, k, x, y, ans;

int get(int x) {
  if (x == fa[x]) return x;
  return fa[x] = get(fa[x]);
}

void merge(int x, int y) { fa[get(x)] = get(y); }

int main() {
  cin >> n >> m;
  for (int i = 1; i <= 3 * n; i++) fa[i] = i;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &k, &x, &y);
    if (x > n || y > n)
      ans++;
    else if (k == 1) {
      if (get(x) == get(y + n) || get(x) == get(y + n + n))
        ans++;
      else {
        merge(x, y);
        merge(x + n, y + n);
        merge(x + n + n, y + n + n);
      }
    } else {
      if (x == y || get(x) == get(y) || get(x) == get(y + n))
        ans++;
      else {
        merge(x, y + n + n);
        merge(x + n, y);
        merge(x + n + n, y + n);
      }
    }
  }
  cout << ans << endl;
}