并查集
并查集
区间染色
长为n的序列，开始均无颜色，
有m个操作，每次将l到r的数全染成c色，
求最终的序列。
我们考虑将染色反着来，则一个数若被染色一次，(题目给的顺序反向做,减少合并次数)
则这就是它的最终颜色，不会改变。
所以下次若在遇到这个数则需要跳过，
也就是对已经染色的区间
以指向右边第一个还没有操作的数。
于是我们令
将i染色后，令
之后就是正常的并查集操作了。
然后这题是个特例，染色虽然是正着来的，但染的颜色全是一种，
只存在0−>1，染一次则以后不变色，所以也可用这种方法做。
P1840
在一条数轴上有 n 个点，分别是 1,2,…,n。一开始所有的点都被染成黑色。接着我们进行 m 次操作，第 i 次操作将 [li,ri] 这些点染成白色。请输出每个操作执行后剩余黑色点的个数。
并查集加速区间染色，更新同色最大编号。
int fa[MAXN];
int n, m;
inline int findfa(int x) {
return fa[x] == x ? (x) : (fa[x] = findfa(fa[x]));
}
signed main() {
int rem = n = read();
m = read();
for (int i = 1; i <= n; i++)fa[i] = i;
while (m--) {
int l = read(), r = read();
r = findfa(r);// r 左边第一个没有被染色的点
while (l <= r) {
rem--;//每合并一次 剩下的原色点 -1
fa[r] = findfa(r - 1);//合并操作
r = findfa(r);//更新右边界
}
cout << rem << "\n";
}
return (1 ^ 0 ^ 1);
}种类并查集
P1525 关押罪犯
种类并查集中“种类”这个词也不是绝对的，它也可以说是一种关系，而本题的关系就在于要将罪犯分配到的两个监狱；我们可以将数组开到两倍来模拟这两个监狱（用A，B表示），每个罪犯在每个监狱中都有一个位置。
假设现在要把两个有仇的罪犯分别放到 A 或 B 中，我们发现如果要满足这一对的要求（即分到的监狱不同），那么如果第一个罪犯在 A 监狱，第二个罪犯必须在 B 监狱，反之也一样。
所以我们可以将 A 监狱中第一个罪犯的位置与 B 监狱中第二个罪犯的位置用并查集维护，即这样合并才能保证分到的监狱不一样。但第一个罪犯不一定只能在 A 监狱，所以我们将 B 监狱中第一个罪犯的位置与 A 监狱中第二个罪犯的位置维护。
而出现矛盾的情况，举个例子： a 和 c 有仇，b 和 c 有仇，那么此时 a 和 c 在不同监狱，b 和 c 也在不同监狱，也就是说 a 和 b 一定在一个监狱。可一旦此时 a 和 b 有仇那么就矛盾了，因为a 和 b 要在不同监狱不然会有矛盾，可 a 和 b 已经在之前判定为必须在同一监狱，所会矛盾，此时就可以直接输出 a 和 b 的仇恨值（原理参见前言的贪心）
还有一种维护是否有敌对关系的写法更加明了，但只能处理两个分类的问题，代码中case1
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 6;
inline int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch >'9') {
if (ch == '-')w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch - '0');
ch = getchar();
}
return x * w;
}
struct A {
int u, v;
int w;
bool operator<(A a)const {
return w > a.w;
}
}g[MAXN];
int n, m;
int fa[MAXN], siz[MAXN];
int enemy[MAXN];
int aa[2 * MAXN], bb[2 * MAXN];
int findfa(int x) {
return fa[x] == x ? (x) : (fa[x] = findfa(fa[x]));
}
inline void merge(int u, int v) {
u = findfa(u), v = findfa(v);
if (u == v)return;
if (siz[u] > siz[v]) { fa[v] = u; siz[u] += siz[v]; }
else { fa[u] = v; siz[v] += siz[u]; }
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
cin >> n >> m;
//贪心排序从大到小
for (int i = 1; i <= m; i++) {
cin >> g[i].u >> g[i].v >> g[i].w;
}
sort(g + 1, g + m + 1);
int faa = g[1].u, fab = g[1].v;
//第一种写法 记录目前有没有敌人 有敌人的话直接将敌人的敌人和自己并起来
//没有敌人就记录敌人
if (rand() % 2) {
for (int i = 1; i <= n; i++)
fa[i] = i, siz[i] = 1;
for (int i = 1; i <= m; i++) {
int u = g[i].u, v = g[i].v;
// cout << g[i].w << "\n";
int fau = findfa(u), fav = findfa(v);
if (fau == fav) {
cout << g[i].w << endl;
return 0;
}
else {
if (!enemy[u])enemy[u] = v;
else merge(enemy[u], v);
if (!enemy[v])enemy[v] = u;
else merge(enemy[v], u);
}
}
}
//第二种写法 在并查集中开二倍数组 分别记录在不同种类的情况
else {
for (int i = 1; i <= n; i++)
fa[i] = i, fa[i + n] = i + n; //初始化不能忘！！！
for (int i = 1; i <= m; i++) {
int u = g[i].u, v = g[i].v;
//只需要check在一个监狱的情况
if (findfa(u) == findfa(v) || findfa(u + n) == findfa(v + n)) {
cout << g[i].w << endl;
return 0;
}
//个人认为是维护敌对关系 因此要开始分两个楼来维护
//两边是可以轮换的 所以无所谓顺序是什么
//下面如果再有连到 u 或者 v+n 的点都必将是对面楼上的
//因此维护了 敌对的关系
fa[fa[u + n]] = fa[v];
fa[fa[v + n]] = fa[u];//维护两罪犯在不同监狱的关系(原作者)
}
}
cout << "0\n";
return (1 ^ 0 ^ 1);
}
//千手千眼观世音菩萨广大圆满无碍大悲心陀罗尼 南无、喝啰怛那、哆啰夜耶,南无、阿唎耶,婆卢羯帝、烁钵啰耶,菩提萨埵婆耶,摩诃萨埵婆耶,摩诃、迦卢尼迦耶,唵,萨皤啰罚曳,数怛那怛写,南无、悉吉栗埵、伊蒙阿唎耶,婆卢吉帝、室佛啰楞驮婆,南无、那啰谨墀,醯利摩诃、皤哆沙咩,萨婆阿他、豆输朋,阿逝孕,萨婆萨哆、那摩婆萨哆,那摩婆伽,摩罚特豆。怛侄他。唵,阿婆卢醯。卢迦帝。迦罗帝。夷醯唎。摩诃菩提萨埵,萨婆萨婆。摩啰摩啰,摩醯摩醯、唎驮孕。俱卢俱卢、羯蒙。度卢度卢、罚阇耶帝。摩诃罚阇耶帝。陀啰陀啰。地唎尼。室佛啰耶。遮啰遮啰。摩么罚摩啰。穆帝隶。伊醯伊醯。室那室那。阿啰参、佛啰舍利。罚沙罚参。佛啰舍耶。呼嚧呼嚧摩啰。呼嚧呼嚧醯利。娑啰娑啰,悉唎悉唎。苏嚧苏嚧。菩提夜、菩提夜。菩驮夜、菩驮夜。弥帝唎夜。那啰谨墀。地利瑟尼那。婆夜摩那。娑婆诃。悉陀夜。娑婆诃。摩诃悉陀夜。娑婆诃。悉陀喻艺。室皤啰耶。娑婆诃。那啰谨墀。娑婆诃。摩啰那啰。娑婆诃。悉啰僧、阿穆佉耶,娑婆诃。娑婆摩诃、阿悉陀夜。娑婆诃。者吉啰、阿悉陀夜。娑婆诃。波陀摩、羯悉陀夜。娑婆诃。那啰谨墀、皤伽啰耶。娑婆诃。摩婆利、胜羯啰夜。娑婆诃。南无、喝啰怛那、哆啰夜耶,南无、阿唎耶。婆嚧吉帝。烁皤啰夜。娑婆诃。唵,悉殿都。漫多啰。跋陀耶,娑婆诃P2024食物链
总体和上题相似，区别在于要维护三个种类间的敌对关系和朋友关系
建立A（1~n）B（1+n~2n）C（1+2n~3n）三个种类
A->B->C->A是一个环状吃的关系
定义a可以吃b是 a在本种类中的点与b在下一个种类中的点在同一个集合中
那么 a与b是朋友的定义即是 在本种类a与下种类b以及本种类b与下种类a均不在同一个集合中
判断后连接朋友在同一种类中
连接敌人在相邻集合中
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXN = 5e4 + 10;
int n, m;
int fa[3 * MAXN];
int findfa(int x) {
return x == fa[x] ? (x) : (fa[x] = findfa(fa[x]));
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i++) {
fa[i] = i; fa[i + n] = i + n; fa[i + 2 * n] = i + 2 * n;
}
for (int i = 1; i <= m; i++) {
int op, u, v;
cin >> op >> u >> v;
if (u > n || v > n) { ans++; continue; }
//同类
if (op == 1) {
//是否有敌对关系
if (findfa(u) == findfa(v + n) || findfa(v) == findfa(u + n))ans++;
else {
fa[findfa(u)] = findfa(v);
fa[findfa(u + n)] = findfa(v + n);
fa[findfa(u + 2 * n)] = findfa(v + 2 * n);
}
}
//u 吃 v
if (op == 2) {
if (u == v) { ans++; continue; }
if (findfa(v) != findfa(u + n) && findfa(u) != findfa(v)) {
fa[findfa(v)] = findfa(u + 2 * n);
fa[findfa(v + n)] = findfa(u);
fa[findfa(v + 2 * n)] = findfa(u + n);
}
else ans++;
}
}
cout << ans << "\n";
return (1 ^ 0 ^ 1);
}
//千手千眼观世音菩萨广大圆满无碍大悲心陀罗尼
//南无、喝啰怛那、哆啰夜耶,南无、阿唎耶,婆卢羯帝、烁钵啰耶,菩提萨埵婆耶,摩诃萨埵婆耶,摩诃、迦卢尼迦耶,唵,萨皤啰罚曳,数怛那怛写,南无、悉吉栗埵、伊蒙阿唎耶,婆卢吉帝、室佛啰楞驮婆,南无、那啰谨墀,醯利摩诃、皤哆沙咩,萨婆阿他、豆输朋,阿逝孕,萨婆萨哆、那摩婆萨哆,那摩婆伽,摩罚特豆。怛侄他。唵,阿婆卢醯。卢迦帝。迦罗帝。夷醯唎。摩诃菩提萨埵,萨婆萨婆。摩啰摩啰,摩醯摩醯、唎驮孕。俱卢俱卢、羯蒙。度卢度卢、罚阇耶帝。摩诃罚阇耶帝。陀啰陀啰。地唎尼。室佛啰耶。遮啰遮啰。摩么罚摩啰。穆帝隶。伊醯伊醯。室那室那。阿参、佛啰舍利。罚沙罚参。佛啰舍耶。呼嚧呼嚧摩啰。呼嚧呼嚧醯利。娑啰娑啰,悉唎悉唎。苏嚧苏嚧。菩提夜、菩提夜。菩驮夜、菩驮夜。弥帝唎夜。那啰谨墀。地利瑟尼那。婆夜摩那。娑婆诃。悉陀夜。娑婆诃。摩诃悉陀夜。娑婆诃。悉陀喻艺。室皤啰耶。娑婆诃。那啰谨墀。娑婆诃。摩啰那啰。娑婆诃。悉啰僧、阿穆佉耶,娑婆诃。娑婆摩诃、阿悉陀夜。娑婆诃。者吉啰、阿悉陀夜。娑婆诃。波陀摩、羯悉陀夜。娑婆诃。那啰谨墀、皤伽啰耶。娑婆诃。摩婆利、胜羯啰夜。娑婆诃。南无、喝啰怛那、哆啰夜耶,南无、阿唎耶。婆嚧吉帝。烁皤啰夜。娑婆诃。唵,悉殿都。漫多啰。跋陀耶,娑婆诃。思维
P1640 连续攻击游戏
借鉴的lishujia巨佬思路如下
想象每个武器的两个攻击值的使用情况，两个攻击的使用互斥所以只有一个值是必用的
因此可以考虑连成大根树（每条边上大下小），假设这个树上没有环，那么树上使用的点是
判断环的方法是并查集，因此可以存储reach数组，表示如果i是祖先节点时能否取到（不是祖先节点无意义）
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define endl '\n'
using namespace std;
const int MAXN = 1e4 + 6;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LLM = 0x3ffffffffffffff;
inline int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch >'9') {
if (ch == '-')w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch - '0');
ch = getchar();
}
return x * w;
}
int fa[MAXN + 10];
bool reach[MAXN + 10];//是否必然能到达(每条边上两点必有一点可以到达)
inline int findfa(int x) {
return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}
signed main() {
int n = read();
for (int i = 1; i < MAXN; i++)fa[i] = i;
for (int i = 1; i <= n; i++) {
int u = findfa(read()), v = findfa(read());
if (u == v)reach[u] = 1;
//两边其中一点如果连边前必达 那么另一点必达
//小点往大点上接
else {
if (u < v)swap(u, v);
fa[v] = u, reach[u] |= reach[v];
}
}
for (int i = 1; i <= n + 1; i++) {
//判断祖先节点是否必达
//判断是否为祖先节点
if (!reach[findfa(i)] && findfa(i) == i) {
cout << i - 1 << "\n";
return 0;
}
}
return (1 ^ 0 ^ 1);
}双倍经验 ARC111B
想象每个卡片的两个两面数字的使用情况，一张牌上两个数字的使用互斥所以只有一个值是必用的。
因此可以考虑连成大根树（每条边上大下小），假设这个树上没有环，那么树上使用的点是
判断环的方法可以采用并查集，因此存储
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 4e5 + 6;
inline int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch >'9') {
if (ch == '-')w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch - '0');
ch = getchar();
}
return x * w;
}
int fa[MAXN + 10];
int siz[MAXN + 10];
int come[MAXN + 10];
bool reach[MAXN + 10];//是否必然能到达(每条边上两点必有一点可以到达)
inline int findfa(int x) {
return x == fa[x] ? x : fa[x] = findfa(fa[x]);
}
signed main() {
int n = read();
for (int i = 1; i < MAXN; i++)fa[i] = i, siz[i] = 1;
for (int i = 1; i <= n; i++) {
int u = findfa(read()), v = findfa(read());
come[u] = come[v] = 1;
if (u == v)reach[u] = 1;
//两边其中一点如果连边前必达 那么另一点必达
//小点往大点上接
else {
if (u < v)swap(u, v);
fa[v] = u, reach[u] |= reach[v];
siz[u] += siz[v];
}
}
int ans = 0;
for (int i = 1; i <= MAXN; i++) {
if (come[i] && findfa(i) == i) {
ans += siz[i];
if (!reach[i])ans--;
}
}
cout << ans << "\n";
return (1 ^ 0 ^ 1);
}