目录
一、板子
题目链接：P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
并查集嘛，顾名思义就是并和查，并就是将 X 与 Y 所在的集合合并。
查就是查询X与Y是否在同一集合内 。
#include<iostream>
#include<string>
using namespace std;
const int M = 1e5;
const int N = 50000;
int Father[M];
int Rank[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
Father[y_root] = x_root;
else if (Rank[x_root] < Rank[y_root])
Father[x_root] = y_root;
else
{
Father[y_root] = x_root;
Rank[y_root]++;
}
}
return 0;
}
int main()
{
int times = 1;
int n, m;
cin >> n >> m;
initialize(n);
for (int i = 0; i < m; i++)
{
int x, y, z;
cin >> z >> x >> y;
if (z == 1)
join(x, y);
else
{
if (find(x) == find(y))
cout << "Y" << endl;
else
cout << "N" << endl;
}
}
}
二、板子改动一点点就行的题
1.亲戚
P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
m次并，p次查。
#include<iostream>
#include<string>
using namespace std;
const int M = 1e5;
const int N = 50000;
int Father[M];
int Rank[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
Father[y_root] = x_root;
else if (Rank[x_root] < Rank[y_root])
Father[x_root] = y_root;
else
{
Father[y_root] = x_root;
Rank[y_root]++;
}
}
return 0;
}
int main()
{
int times = 1;
int n, m,p;
cin >> n >> m>>p;
initialize(n);
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
join(x, y);
}
for(int i=0;i<p;i++)
{
int x, y;
cin >> x >> y;
if (find(x) == find(y))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
2.SKA-Piggy Banks
一道不懂为什么是绿的题，明明就是个板子（）；
输出有多少个父亲就行；
传送门：P3420 [POI2005]SKA-Piggy Banks - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<iostream>
#include<string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int M = 2e6;
const int N = 50000;
ll Father[M];
ll Rank[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
{
Father[y_root] = x_root;
}
else if (Rank[x_root] < Rank[y_root])
{
Father[x_root] = y_root;
}
else
{
Father[y_root] = x_root;
Rank[x_root]++;
}
}
return 0;
}
int main()
{
ll n,ans=0;
cin >> n ;
initialize(n);
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
join(x, i);
}
for (int i = 1; i <= n; i++)
{
if (find(i) == i)
ans++;
}
cout << ans << endl;
}
三、修复公路
传送门：P1111 修复公路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目是给出了很多道路，和修路的时间，问修路修到每个村庄可以互通的最短时间。
没看出来是个并查集抱歉QAQ。
如果用并查集写，其实也很好想，就是先把每个村庄看作单独的连通块（即一开始有n个连通块，每个点的父亲都是自己，即initialize函数）
然后注意要对修路的时间排序，因为希望所用时间越短越好（这里存边用了pair套pair，凭感觉用了一下，感觉还挺不擦）
然后就是遍历时间升序的road啦~，注意的就是要先看看两个村子是不是已经连在一起了（看他们的父亲是不是相同就行），如果没连，让其中一个人当父亲都行，这样相连的村子数++。
下面两个代码，第一个没有rank和join，因为也用不到其实，直接给父亲数组赋值就行。
第二个就和板子很像了，不过效果是差不多。
#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
const int M = 2e5;
const int N = 50000;
int Father[M];
pair<int, pair<int, int> >road[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int main()
{
int times = 1;
int n, m,sum=0,ans=0;
cin >> n >> m;
initialize(n);
for (int i = 1; i <=m; i++)
{
int x, y, t;
cin >> road[i].second.first >> road[i].second.second >> road[i].first;
}
sort(road+1, road+1 + m);
for (int i = 1; i <= m; i++)
{
int x = find(road[i].second.first);
int y = find(road[i].second.second);
if (x != y)//如果原先不连通
{
Father[x] = y;
ans = max(ans, road[i].first);
n--;//合并后连通块数量--
if (n == 1)//只剩一个连通块，即任意两个村庄可以联通
{
cout << ans << endl;
return 0;
}
}
}
cout << "-1\n";
}
第二段：
#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
const int M = 2e5;
const int N = 50000;
int Father[M];
int Rank[M];
pair<int, pair<int, int> >road[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
Father[y_root] = x_root;
else if (Rank[x_root] < Rank[y_root])
Father[x_root] = y_root;
else
{
Father[y_root] = x_root;
Rank[y_root]++;
}
}
return 0;
}
int main()
{
int times = 1;
int n, m,sum=0,ans=0;
cin >> n >> m;
initialize(n);
for (int i = 1; i <=m; i++)
{
int x, y, t;
cin >> road[i].second.first >> road[i].second.second >> road[i].first;
}
sort(road+1, road+1 + m);
for (int i = 1; i <= m; i++)
{
int x = road[i].second.first;
int y = road[i].second.second;
if (find(x) == find(y))//已经是联通的了
continue;
join(x, y);
ans = max(ans, road[i].first);
sum++;
if (sum== n-1)//联通个数为n-1，即村庄间都通了
{
cout << ans << endl;
return 0;
}
}
cout << "-1\n";
}
四、繁忙的都市
传送门：
P2330 [SCOI2005]繁忙的都市 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
其实和三的代码一模一样，就多了一行（流汗猫猫头）
#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
const int M = 2e5;
const int N = 50000;
int Father[M];
int Rank[M];
pair<int, pair<int, int> >road[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
Father[y_root] = x_root;
else if (Rank[x_root] < Rank[y_root])
Father[x_root] = y_root;
else
{
Father[y_root] = x_root;
Rank[y_root]++;
}
}
return 0;
}
int main()
{
int times = 1;
int n, m, sum = 0, ans = 0,anss=0;
cin >> n >> m;
initialize(n);
for (int i = 1; i <= m; i++)
{
int x, y, t;
cin >> road[i].second.first >> road[i].second.second >> road[i].first;
}
sort(road + 1, road + 1 + m);
for (int i = 1; i <= m; i++)
{
int x = road[i].second.first;
int y = road[i].second.second;
if (find(x) == find(y))//已经是联通的了
continue;
join(x, y);
anss++;
ans = max(ans, road[i].first);
sum++;
if (sum == n - 1)//联通个数为n-1，即都通了
{
cout <<anss<<" "<< ans << endl;
return 0;
}
}
}
五、炸铁路
传送门：P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
emmm，用笨办法擦边ac属于是。
因为边也不多，所以就是遍历删除每一条边看能不能联通，不能联通就记录一下这条边，注意排序输出就行。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int M = 1e3;
const int N = 50000;
int Father[M];
int Rank[M];
int times = 1, anss = 0;
int n, m;
pair<int, int> road[M];
pair<int, int> ans[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
Father[y_root] = x_root;
else if (Rank[x_root] < Rank[y_root])
Father[x_root] = y_root;
else
{
Father[y_root] = x_root;
Rank[y_root]++;
}
}
return 0;
}
void solve(int out)
{
times = 1;
int fa=0,i;
initialize(n);
for (i = 0; i < m; i++)
{
if (i == out)
continue;
if (find(road[i].first) != find(road[i].second))
join(road[i].first, road[i].second);
}
for (fa = find(1), i = 2; i <= n; i++)
{
if (find(i) != fa)
{
ans[anss].first = road[out].first, ans[anss++].second = road[out].second;
return;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
if (x > y)
road[i].second = x, road[i].first = y;
else
road[i].second = y, road[i].first = x;
//join(road[i].first, road[i].second);
}
for (int i = 0; i < m; i++)
{
solve(i);
}
sort(ans, ans + anss);
for (int i = 0; i < anss; i++)
{
cout << ans[i].first << " " << ans[i].second << endl;
}
}
六、搭配购买
传送门：P1455 搭配购买 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
并查集+dp
并查集来合并集合，然后把一个集合里的看作一个大的物品去dp就行。
注意的点：
1.合并价值的时候，合并的是点，不是合并两个父亲的价值
Money[y_root] += perm[x]; Value[y_root] += perv[x];
2.合并之后，为了dp方便，作为儿子的所有物品都变成0
（不然会在第五个点一直wa)
#include<iostream>
#include<string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int M = 2e6;
const int N = 50000;
ll Father[M],dp[M];
ll Money[M],Value[M];
ll perm[M];
ll perv[M];
ll Rank[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Money[i] = perm[i];
Value[i] = perv[i];
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
{
Father[y_root] = x_root;
Money[x_root] += perm[y];
Value[x_root] += perv[y];
}
else if (Rank[x_root] < Rank[y_root])
{
Father[x_root] = y_root;
Money[y_root] += perm[x];
Value[y_root] += perv[x];
}
else
{
Father[y_root] = x_root;
Money[x_root] += perm[y];
Value[x_root] += perv[y];
Rank[x_root]++;
}
}
return 0;
}
int main()
{
ll n, m, mon;
cin >> n >> m>>mon;
for (int i = 1; i <= n; i++)
cin >> perm[i] >> perv[i];
initialize(n);
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
join(x, y);
}
for (int i = 1; i <= n; i++)
{
if (i != find(i))
{
Value[i] = 0;
Money[i] = 0;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = mon; j >= Money[i]; j--)
{
dp[j] = max(dp[j], dp[j - Money[i]] + Value[i]);
}
}
cout << dp[mon] << endl;
}
七、种类并查集--关押罪犯
传送门：P1525 [NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
贪心思想：使怒气值大的一对人尽量不在同一间监狱里 ，所以先要排序（没错，我又用了pair套pair，嘻嘻）
题解思想：如果a，b有仇，那么把他们放在一起显然不合理，还不如把a与b的其他敌人放在一起，如果恰好a与b的其他敌人之间没有矛盾，那么他们就可以放在同一个集合中。
排完序我们就开始遍历罪犯关系。这个时候并查集合并的是某个人现有的所有敌人（无论敌人之间的关系是不是和睦），当发现关系中的两个人已经不知不觉在同一个牢笼里（同一个父亲），说明已经找到最大怒气值了，直接就输出~
#include<iostream>
#include<string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int M = 2e6;
const int N = 50000;
ll Father[M];
ll Rank[M];
ll Enemy[M];
pair<int, pair<int, int> >people[M];
void initialize(int n)
{
for (int i = 1; i <= n; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
{
Father[y_root] = x_root;
}
else if (Rank[x_root] < Rank[y_root])
{
Father[x_root] = y_root;
}
else
{
Father[y_root] = x_root;
Rank[x_root]++;
}
}
return 0;
}
int main()
{
ll n,m,ans=0;
cin >> n>>m ;
initialize(n);
for (int i = 1; i <= m; i++)
{
cin >> people[i].second.first >> people[i].second.second >> people[i].first;
}
sort(people + 1, people + 1 + m);
for (int i = m; i>=1; i--)
{
ll x = people[i].second.first;
ll y = people[i].second.second;
if ( x==y )
{
cout << people[i].first << endl;
return 0;
}
if (find(x)==find(y))
{
cout << people[i].first<<endl;
return 0;
}
//把敌人的敌人自己分为一组
if(!Enemy[x])
{
Enemy[x] = y;
}
else
{
join(Enemy[x], y);
}
//另一个人
if (!Enemy[y])
{
Enemy[y] = x;
}
else
{
join(Enemy[y], x);
}
}
cout <<0<< endl;
}
八、经典的种类并查集---食物链
先说一下种类并查集吧，因为并查集有传递性连通性的特点，所以在一个集合里的就是一家人，简称“朋友的朋友也是朋友”，不过敌人的敌人不一定是敌人，就像上一个关押罪犯的题。
所以就有了种类并查集：
常见的做法是将并查集扩大倍数，并划分种类。在同个种类的并查集中合并，表示的仍然是朋友。但是要在合并的时候考虑到在不同种类，其实就是说他们是敌人。
这个题有三个种类，我们就开三倍的n（注意初始化函数也要改一改奥）；
一倍空间放同类，二倍空间放食物，三倍空间放天敌；
之后考虑如果是真话（这个用find判断一下是不是符合就行），我们需要合并相应的集合。
如果是假话（包括find判断结果错误和x>n||y>n），ans++。
最后说一下合并集合这块：
这个食物链关系真是理的我头大，咱们看下面这个图吧，捕食天敌什么的，QAQ人家真的不行。
希望下面的图可以有点帮助：
#include<iostream>
#include<string>
#include <algorithm>
typedef long long ll;
using namespace std;
const int M = 2e6;
const int N = 50000;
ll Father[M];//一倍空间放同类，二倍空间放食物，三倍空间放天敌
ll Rank[M];
ll Enemy[M];
//朋友的朋友就是朋友（普通并查集） ，但敌人的敌人也是朋友（维护这种关系就是种类并查集了）
//种类并查集
void initialize(int n)
{
for (int i = 1; i <= n*3; i++)
{
Father[i] = i;
Rank[i] = 0;
}
}
int find(int x)
{
return Father[x] == x ? x : (Father[x] = find(Father[x]));
}
int join(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root)
return 1;
else
{
if (Rank[x_root] > Rank[y_root])
{
Father[y_root] = x_root;
}
else if (Rank[x_root] < Rank[y_root])
{
Father[x_root] = y_root;
}
else
{
Father[y_root] = x_root;
Rank[x_root]++;
}
}
return 0;
}
int main()
{
ll n,m,ans=0;
cin >> n>>m ;
initialize(n);
for (int i = 1; i <= m; i++)
{
int type, x, y;
cin >> type >> x >> y;
if (x > n || y > n)
{
ans++;
continue;
}
if (type == 1)
{
//他说他们是同类，我们就看看他们是不是食物或者天敌
//如果都不是，那说明是真话咯
if (find(x) == find(y + n) || find(x) == find(y + 2 * n))
ans++;
else//真话，咱记录一下
{
join(x, y);//x与y是同类
join(x + n, y + n);//x与y的食物也是同类
join(x + 2 * n, y + 2 * n);//他们的天敌也是同类
}
}
else
{
//他说他们是x是y的天敌，我们就看看他们是不是同类或者x是y的猎物
//如果都不是，那说明是真话咯
if (find(x) == find(y) || find(x+2*n) == find(y))
ans++;
else//真话，咱记录一下
{
join(x+n, y);//y 是 x的食物（x+n）
join(x, y + 2 * n);//y+n吃x ,y的天敌（y+2n)与a是一类
join(x+2*n, y+n);//y吃x+2n，y和x的食物（x+n）一类
}
}
}
cout << ans << endl;
}