1 问题
有
- 同类:
的类别相同。 - 异类:
的类别相反。
每次判断新关系能否与已经接受的关系同时成立。相容就接受,矛盾就拒绝,继续处理下一条。
例如,已知
并查集 可以合并同类元素,但不能把异类元素直接合并。种类并查集通过拆点,把类别之间的关系转为普通并查集中的等价关系。
2 两种身份
为每个元素
| 编号 | 含义 |
|---|---|
| 与 |
记
并查集中的“同属一个集合”表示:这些身份被已有关系强制为同一类别。它不是在预先指定哪个集合叫第一类、哪个叫第二类。
若
因此把
每条约束都对两个身份对称处理,这样后续才能继续正确传递关系。
3 合并规则
3.1 同类
要求
unite(x, y);
unite(x + n, y + n);
加入前若已有
3.2 异类
要求
unite(x, y + n);
unite(x + n, y);
加入前若已有
| 新约束 | 冲突条件 | 通过后执行 |
|---|---|---|
| 同类 | 合并 |
|
| 异类 | 合并 |
先检查,再合并。 矛盾关系不应进入并查集;查询时发生路径压缩没有问题,因为它不改变已有关系。
3.3 未知关系
两个真实元素的根不同,不一定表示它们异类。它们可能还没有任何联系。
if (same(x, y)) {
// 已知同类
} else if (same(x, y + n)) {
// 已知异类
} else {
// 关系未知
}
例如刚初始化时,
4 冲突示例
先接受
再接受
传递后,两组等价身份分别是
所以新关系“
5 正确性
每个相容的关系连通块,都对应一对相反的身份集合。选择其中一组为第一类,另一组为第二类,就给出了这个连通块的一种合法分类。不同连通块可以独立选择,类别名称本身不影响同类、异类关系。
加入新关系时:
- 若两端关系已经确定,冲突条件会拒绝相反要求;重复的相同要求仍然合法。
- 若两端尚无联系,可以整体翻转其中一个连通块的两类,使新约束成立,再按规则连接两对身份集合。
因此,规则恰好拒绝无法满足的新关系。接受后,正反身份仍保持相反,所有同类关系由普通并查集正确传递。
6 代码
下面使用本篇的在线判定格式。第一行输入
0 x y:要求同类。1 x y:要求异类。
每条约束输出 YES 或 NO。YES 表示与之前接受的约束相容,包括重复关系;NO 表示拒绝当前约束。它不表示每条关系都成功合并了两个原本不同的集合。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
int fa[maxn * 2], sz[maxn * 2];
void init(int count) {
for (int i = 1; i <= count; ++i) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
}
// op=0 要求同类,op=1 要求异类;矛盾时拒绝这条关系。
bool add_relation(int op, int x, int y, int n) {
if (op == 0) {
if (same(x, y + n)) return false;
unite(x, y);
unite(x + n, y + n);
} else {
if (same(x, y)) return false;
unite(x, y + n);
unite(x + n, y);
}
return true; // 相容的重复关系也返回 true
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
init(2 * n); // x 表示自身身份,x+n 表示相反身份
while (m--) {
int op, x, y;
cin >> op >> x >> y;
cout << (add_relation(op, x, y, n) ? "YES" : "NO") << '\n';
}
return 0;
}
输入:
4 6
1 1 2
1 2 3
0 1 3
1 1 3
0 3 4
1 2 4
输出:
YES
YES
YES
NO
YES
YES
前两条关系推出
7 二分图
若所有约束都是“异类”,就得到二分图判定:
- 每个真实元素是一个点。
- 一条边要求两端颜色相反。
- 每条边用两次交叉合并表示。
沿边走一次,颜色翻转一次。偶数长度路径要求两端同色,奇数长度路径要求两端异色;奇环会要求起点与自身异色,产生冲突。
固定图也可以用 DFS、BFS 染色。种类并查集适合按顺序加入约束、随时检查冲突的场景。
8 三类关系
8.1 食物链
luogu P2024: [NOI2001] 食物链 有三类动物,关系为
两类中,“异类的异类”必定同类;三类中不能这样推断。例如
| 编号 | 含义 |
|---|---|
| 吃 |
三个身份依次按“吃”循环,第三个身份的猎物又回到第一个身份。它们仍是相对身份,不表示已经知道
若
| 新关系 | 三组应合并的身份 |
|---|---|
这里
8.2 检查与合并
沿用上述身份约定:
- 声称同类时,若已有
same(x, y+n)或same(x, y+2*n),则矛盾。 - 声称
吃 时,若已有 same(x, y)或same(x, y+n),则矛盾。
可以把两种关系统一成偏移量:
int shift = (op == 1 ? 0 : 2);
for (int k = 0; k < 3; ++k) {
if (k != shift && same(x, y + k * n)) return false;
}
for (int k = 0; k < 3; ++k) {
unite(x + k * n, y + (k + shift) % 3 * n);
}
先排除两种错误关系,再合并三组对应身份。编号越界的说法也是假话,必须在访问数组前检查;“
每个关系连通块的三组身份保持循环对应。连接两个原本无关的块时,可以整体轮换其中一块的类别编号,使新关系成立;已经相连时,两端关系已经确定,核对它是否符合本次说法即可。这与二类模型中“整体翻转一个块”的论证相同。
食物链完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50000 + 5;
int fa[maxn * 3], sz[maxn * 3];
void init(int count) {
for (int i = 1; i <= count; ++i) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
}
// x、x+n、x+2n 分别代表 x 自身、x 的猎物、x 的天敌的类别。
bool add_statement(int op, int x, int y, int n) {
int shift = (op == 1 ? 0 : 2); // 同类:x~y;x 吃 y:x~y+2n
for (int k = 0; k < 3; ++k) {
if (k != shift && same(x, y + k * n)) return false;
}
// 检查通过后再统一合并,不能把假话写入并查集。
for (int k = 0; k < 3; ++k) {
unite(x + k * n, y + (k + shift) % 3 * n);
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
init(3 * n);
int answer = 0;
while (m--) {
int op;
long long x, y; // 题目允许越界编号,先用宽类型读取再验证
cin >> op >> x >> y;
if (x < 1 || x > n || y < 1 || y > n) {
++answer;
continue;
}
if (!add_statement(op, (int)x, (int)y, n)) ++answer;
}
cout << answer << '\n';
return 0;
}
编号先用 long long 读取。题目允许输入超过 int 范围的编号,不能先缩窄为 int 再检查。每条假话只计数,不写入并查集。
9 复杂度与边界
拆成固定的
- 数组容量与初始化范围都要扩大到
或 。二类模板支持 ,食物链模板支持 。 - 不同连通块之间的关系可能未知,不能把“根不同”当作“已知异类”。
- 辅助身份不是实际元素。若统计真实元素的分组,只枚举原来的
。 - 模板中的
sz统计的是拆点后的身份数,只用于按大小合并,不能直接当作真实元素人数。 - 若题目要求所有约束同时成立,任何一次冲突都应使最终答案为否,不能因后续关系被接受而恢复为是。
- 拆点依赖题目给出的类别规则。不能把现实中的敌友、食物关系自行理解为二类对立或三类循环。
10 练习
10.1 手算
- 初始只有两个真实元素,根不同,能否断定它们异类?
- 连续要求
同类、 异类,分别是否成立? - 食物链中,已知
吃 、 吃 ,可以推出哪条关于 的关系?
参考结果
- 不能,关系未知。
- 同类成立,异类矛盾;拒绝后仍保留此前的合法关系。
吃 ,不是 吃 ,也不是同类。三类循环的方向不能颠倒。
10.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 二类基础 | AtCoder ABC327 D:Good Tuple Problem | 每条关系都要求异类,整体判断能否二染色。输入先给完整的 |
| 排序应用 | luogu P1525: [NOIP 2010 提高组] 关押罪犯 | 按怨气值降序要求两人异类;首次冲突的权值是答案,无冲突则为 |
| 三类推广 | luogu P2024: [NOI2001] 食物链 | 明确三个相对身份,检查矛盾与非法编号,再执行三次合并。 |
关押罪犯按降序处理,是为了优先避免更大的同监狱冲突。首次在权值
若希望直接在边上记录类别差,而不是建立多个身份,可继续阅读 带权并查集。
11 相关题解
暂无相关题解