并查集 #

普通并查集 #

LG P1955 [NOI2015] 程序自动分析 #

现在存在 $10^9$ 个变量和 m 条关系，关系一定是两个变量相等和不等两种，问这些变量满足关系下是否有解 $1 \leq n \leq 10^5$

• 注意和下面扩展域并查集中敌人的区别，我开始就搞错了。关键在于与同一个数不等的两个数可以等也可以不等但敌人的敌人一定是朋友
• 所以普通并查集先处理相等再遍历一次判断不等是否满足即可

扩展域并查集 #

LG P1525 [NOIP 2010 提高组] 关押罪犯 #

给定 $n$ 个人和 $m$ 个带权关系，要求将 $n$ 个人分成两组，使得两组内部存在的关系权值的最大值最小，这个值是多少，可以做到无关系输出 $0$ $1 \leq n \leq 2 \times 10^4, 1 \leq m \leq 10^5$

• 扩展域并查集可以处理将给定关系尽可能不存在一个集合里
• 貌似可以二分图做

CF400 776 D. The Door Problem #

给定 $n$ 扇门，初始时他们中有的锁住有点没有被锁，存在 $m$ 个按钮，每个按钮按下可同时转换特定若干门的状态，保证每个门恰好被两个按钮控制。问可不可以操作一些按钮使得所有门均打开 $2 \leq n, m \leq 10^5$

• 如何思考状态是这种题的核心
• 注意到一个按钮按超过 2 次无意义
• 设计每一个按钮对应 $i$ 和 $i + m$ 两个状态，表示按或不按，遍历每个门状态产生这 $2 * m$ 个状态的分配情况，最后判断是否存在一个按钮两种状态冲突

LG P1892 [BalticOI 2003] 团伙 #

给定 n 个人和 m 种关系，关系包括朋友和敌人，注意朋友的朋友是朋友，敌人的敌人是朋友，若两个人能属于同一个集合当且仅当他们是朋友，问最少有多少个集合 $2 \leq n \leq 10^3, 1 \leq m \leq 5 \times 10^3$

• 注意时间复杂度是 $O(n\alpha(n))$，数据较弱
• 使用扩展域并查集处理敌人关系，也可以用普通并查集，但需要维护每一个人的第一个敌人

LG https://www.luogu.com.cn/problem/P2024 #

存在一个三元循环的食物链，现在有 $n$ 个生物属于食物链中的一种生物，下标从 $1$ 开始标号，给定 $m$ 条信息，每当信息错误或者与前面矛盾时忽略，问一共有多少信息被忽略。 $m$ 条信息有两种，一种是给定两个生物属于同种生物，一种是给定两个生物存在前对后的捕食关系 $1 \leq n \leq 5 \times 10^4, 1 \leq m \leq 10^5$

• 不同于上面几个二元关系，这里存在三元关系，开三倍并查集可做
• 不过实际上可以使用带权并查集解决(权值取模)，并且感觉可扩展性更好

带权并查集 #

几个模板题： LG P8779 [蓝桥杯 2022 省 A] 推导部分和 对于一个 $n$ 元数列 $a_i$ 给出 $m$ 个一些子数组和，$q$ 次询问另一些子数组和 $1 \leq n, m, q \leq 10^5, -10^{12} \leq a_i \leq 10^{12}$

LG P2294 [HNOI2005] 狡猾的商人 类似的给出 $n$ 元数组的 $m$ 组子数组和，问是否自洽 $1 \leq n \leq 100, 1 \leq m \leq 10^3$ 不过由于数据小倒是出现了很多神秘做法(比如差分约束 + spfa，区间DP等)，但并查集大概是最优的

hdu3038 How Many Answers Are Wrong 类似于上一题

LG P1196 [NOI2002] 银河英雄传说 #

给定 $n = 3 \times 10^4$ 个人排队，编号从 $1$ 开始，现在进行 $m$ 个操作，每次操作分为两种

1. 输入 $i$ 和 $j$，将 $j$ 所在队伍合并到 $i$ 所在队伍末尾
2. 输入 $i$ 和 $j$，返回 $i$ 和 $j$ 在同一队伍中之间的人数，不在一个队伍返回 $-1$

$1 \leq m \leq 5 \times 10^5$

• 注意不能直接用模板中的启发式合并了，要用需要自己在外部进行判断，因为权值和队伍人数相关

hdu3234 Exclusive-OR #

存在 $n$ 个未知的正整数，给出 $q$ 条信息或询问，有三种类型

1. 给出下标为 $i$ 的数的值
2. 给出下标为 $i$ 和 $j$ 的数的异或值
3. 在线根据前面的信息，询问给出的 $k$ 个下标的异或值，或返回不能确定

另外当信息冲突时终止这组测试 $1 \leq T \leq 10$ 组样例，$1 \leq n \leq 2 \times 10^4, 1 \leq m \leq 4 \times 10^4, 1 \leq k \leq 15$

• 需要使用异或带权并查集
• 为了统一两种信息，我们需要设定权值总为 0 的虚点，还要注意去掉启发式合并并且保证虚点总是根
• 处理查询时需要统计这个数字的根节点是否出现偶数次，注意虚点除外
• 这个题的输入输出依托，不建议重新写，虽然这个题本身有价值

小白月赛123 F 明弦音 #

给定 $n$ 个变量 $a_i$，维护三种操作

1. 给定 $u, v, w$ 限制 $a_u - a_v = w$，若矛盾则不进行，并返回报错信息，否则进行限制并返回确定信息
2. 给定 $u, w$ 限制 $a_u = w$，若矛盾则不进行，并返回报错信息，否则进行限制并返回确定信息
3. 给定 $u, v$ 查询 $a_u - a_v$，若未知则返回报错信息

• 第二种操作搭配 $0$ 做虚点，就是带权并查集板子