并查集详解
并查集
并查集是一种树形数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。
具体详解见此
并查集本身是真的太板了。。普及-以下的题基本全是板。
直接见例题吧：
板子一
【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
【】输入格式】
第一行包含两个整数 \(N,M\) ,表示共有 \(N\) 个元素和 \(M\) 个操作。
接下来 \(M\) 行，每行包含三个整数 \(Z_i,X_i,Y_i\) 。
当 \(Z_i=1\) 时，将 \(X_i\) 与 \(Y_i\) 所在的集合合并。
当 \(Z_i=2\) 时，输出 \(X_i\) 与 \(Y_i\) 是否在同一集合内，是的输出
Y ；否则输出 N 。
【输出格式】
对于每一个 \(Z_i=2\) 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
【样例输入 】
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
【样例输出 】
N
Y
N
Y
【提示】
对于 \(30\%\) 的数据，\(N \le 10\)，\(M \le 20\)。
对于 \(70\%\) 的数据，\(N \le 100\)，\(M \le 10^3\)。
对于 \(100\%\) 的数据，\(1\le N \le 10^4\)，\(1\le M \le 2\times 10^5\)，\(1 \le X_i, Y_i \le N\)，\(Z_i \in \{ 1, 2 \}\)。
解析
如题所见，纯板子，我连代码注释都不想写。但还是要说一下抄板子一定要看清楚，如果板子哪个for循环里面和你自身循环用法的习惯不一样可能就大寄了。（代价就是找了一天才找出来）。
code
全是板子有啥好注释的（
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
int pre[maxn],rk[maxn];
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
void init(int n){
for(int i=1;i<=n;i++){
pre[i]=i;
rk[i]=1;
}
}
/*int find(int x){
if(pre[x]==x) return x;
return find(pre[x]);
}*/
int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
bool join(int x,int y){
x=find(x);
y=find(y);
if(x==y) return false;
if(rk[x]>rk[y]) pre[y]=x;
else{
if(rk[x]==rk[y]) rk[y]++;
pre[x]=y;
}
return true;
}
int n,m,z;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();m=read();
init(n);
while(m--){
z=read();
int x=read(),y=read();
if(z==1) join(x,y);
if(z==2){
//cout<<find(x)<<" "<<find(y)<<endl;
if(find(x)==find(y)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
}
板子二
亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
【题目描述】
规定：\(x\) 和 \(y\) 是亲戚，\(y\) 和 \(z\) 是亲戚，那么 \(x\) 和 \(z\) 也是亲戚。如果 \(x\)，\(y\) 是亲戚，那么 \(x\) 的亲戚都是 \(y\) 的亲戚，\(y\) 的亲戚也都是 \(x\) 的亲戚。
【输入格式】
第一行：三个整数 \(n,m,p\)，（\(n,m,p \le 5000\)），分别表示有 \(n\) 个人，\(m\) 个亲戚关系，询问 \(p\) 对亲戚关系。
以下 \(m\) 行：每行两个数 \(M_i\)，\(M_j\)，\(1 \le M_i,~M_j\le n\)，表示 \(M_i\) 和 \(M_j\) 具有亲戚关系。
接下来 \(p\) 行：每行两个数 \(P_i,P_j\)，询问 \(P_i\) 和 \(P_j\) 是否具有亲戚关系。
输出格式
\(p\) 行，每行一个 Yes 或 No。表示第 \(i\) 个询问的答案为“具有”或“不具有”亲戚关系。
【样例输入】
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
【样例输出】
Yes
Yes
No
解析
没啥好讲的，但是一个==写成=是真能把人卡一个上午QAQ。
code
依旧没有注释
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
int pre[maxn],rk[maxn];
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
void init(int n){
for(int i=0;i<n;i++){
pre[i]=i;
rk[i]=1;
}
}
/*int find(int x){
if(pre[x]==x) return x;
return find(pre[x]);
}*/
int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
bool join(int x,int y){
x=find(x);
y=find(y);
if(x==y) return false;
if(rk[x]>rk[y]) pre[y]=x;
else{
if(rk[x]==rk[y]) rk[y]++;
pre[x]=y;
}
return true;
}
int n,m,p;
signed main(){
n=read();m=read();p=read();
init(n);
while(m--){
int i=read(),j=read();
join(i,j);
}
while(p--){
int i=read(),j=read();
if(find(i)==find(j)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
板子三
修复公路
题目背景
A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
【题目描述】
给出 A 地区的村庄数 \(N\)，和公路数 \(M\)，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。
【输入格式】
第 \(1\) 行两个正整数 \(N,M\)。
下面 \(M\) 行，每行 \(3\) 个正整数 \(x,y,t\)，告诉你这条公路连着 \(x,y\) 两个村庄，在时间 \(t\) 时能修复完成这条公路。
【输出格式】
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 \(-1\)，否则输出最早什么时候任意两个村庄能够通车。
【样例输入】
4 4
1 2 6
1 3 4
1 4 5
4 2 3
【样例输出 】
5
【提示】
\(1\leq x, y\leq N \le 10 ^ 3\)，\(1\leq M, t \le 10 ^ 5\)。
解析
板板板，不过好像也因为不知名错误卡了蛮久。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
int pre[maxn],rk[maxn];
struct node{
int x,y,t;
}a[maxn];
bool cmp(node a1,node a2){
return a1.t<a2.t;
}
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
void init(int n){
for(int i=1;i<=n;i++){
pre[i]=i;
rk[i]=1;
}
}
/*int find(int x){
if(pre[x]==x) return x;
return find(pre[x]);
}*/
int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
bool join(int x,int y){
x=find(x);
// cout<<pre[x]<<" ";
y=find(y);
//cout<<pre[y]<<endl;
if(x==y) return false;
if(rk[x]>rk[y]) pre[y]=x;
else{
if(rk[x]==rk[y]) rk[y]++;
pre[x]=y;
}
return true;
}
bool jud(int n){
int sum=0;
for(int i=1;i<=n;i++){
if(find(i)==i) sum++;
//cout<<sum<<endl;
if(sum>1) return false;
}
return true;
}
int n,m;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read(),m=read();
init(n);
for(int i=1;i<=m;i++){
a[i].x=read();
a[i].y=read();
a[i].t=read();
}
sort(a+1,a+m+1,cmp);
//for(int i=1;i<=m;i++) cout<<a[i].t<<" ";
//cout<<endl;
//for(int i=1;i<=m;i++) cout<<a[i].y<<" ";
//cout<<endl;
for(int i=1;i<=m;i++){
join(a[i].x,a[i].y);
if(jud(n)){
cout<<a[i].t<<endl;
return 0;
}
//cout<<a[i].t<<endl;
//for(int i=1;i<=m;i++) cout<<a[i].t<<" ";
//cout<<endl;
//for(int i=1;i<=n;i++) cout<<pre[i]<<" ";
//cout<<endl;
}
cout<<-1<<endl;
}
板子四
板子太多了，编辑也是一种折磨
朋友
题目背景
小明在 A 公司工作，小红在 B 公司工作。
【题目描述】
这两个公司的员工有一个特点：一个公司的员工都是同性。
A 公司有 \(N\) 名员工，其中有 \(P\) 对朋友关系。B 公司有 \(M\) 名员工，其中有 \(Q\) 对朋友关系。朋友的朋友一定还是朋友。
每对朋友关系用两个整数 \((X_i,Y_i)\) 组成，表示朋友的编号分别为 \(X_i,Y_i\)。男人的编号是正数，女人的编号是负数。小明的编号是 \(1\)，小红的编号是 \(-1\)。
大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
【输入格式】
输入的第一行，包含 \(4\) 个空格隔开的正整数 \(N,M,P,Q\)。
之后 \(P\) 行，每行两个正整数 \(X_i,Y_i\)。
之后 \(Q\) 行，每行两个负整数 \(X_i,Y_i\)。
【输出格式】
输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
【样例输入】
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
【样例输出】
2
【提示】
对于 \(30 \%\) 的数据，\(N,M \le 100\)，\(P,Q \le 200\)；
对于 \(80 \%\) 的数据，\(N,M \le 4 \times 10^3\)，\(P,Q \le 10^4\)；
对于 \(100 \%\) 的数据，\(N,M \le 10^4\)，\(P,Q \le 2 \times 10^4\)。
解析
此题相较上几题的不同在于需分成两个并查集，由于有负数，所以可以使用map，是并查集+stl的组合
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
map<int,int>pre,rk;
int n,m,p,q,nu1,nu2;
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
void init(int n,int m){
for(int i=1;i<=n;i++){
pre[i]=i;
rk[i]=1;
}
for(int i=-1;i>=-m;i--){
pre[i]=i;
rk[i]=1;
}
}
int find(int a){
if(a==pre[a]) return a;
return pre[a]=find(pre[a]);
}
bool join(int a,int b){
a=find(a);b=find(b);
if(a==b) return false;
if(rk[a]>rk[b]) pre[b]=pre[a];
else{
if(rk[a]==rk[b]) rk[b]++;
pre[a]=pre[b];
}
return true;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();m=read();p=read();q=read();
init(n,m);
while(p--) join(read(),read());
while(q--){
join(read(),read());
//for(int i=-1;i>=-m;i--) cout<<find(i)<<" ";
//cout<<endl;
}
// for(int i=1;i<=n;i++) cout<<find(i)<<" ";
//cout<<endl;
for(int i=1;i<=n;i++) if(find(1)==find(i)) nu1++;
//for(int i=-1;i>=-m;i--) cout<<find(i)<<" ";
// cout<<endl;
//cout<<find(-5)<<" "<<find(-1)<<endl;
for(int i=-1;i>=-m;i--) if(find(-1)==find(i)) nu2++;
// cout<<nu1<<" "<<nu2<<endl;
if(nu1>nu2) cout<<nu2<<endl;
else cout<<nu1<<endl;
}
板子五
一中校运会之百米跑
题目背景
在一大堆秀恩爱的 ** 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 \(100\) 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。
可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。。。如果你帮助体育老师解决了问题，老师就会给你 \(5\) 个积分。
【题目描述】
假设一共有 \(N\)（\(2\leq N\leq 2\times 10^4\)）个参赛选手。（尼玛全校学生都没这么多吧）
老师会告诉你这 \(N\) 个选手的名字。
接着会告诉你 \(M\)（\(1\leq M\leq 10^6\)）句话，即告诉你学生 A 与学生 B 在同一个组里。
如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。
然后老师会问你 \(K\)（\(1\leq K\leq 10^6\)）句话，即学生 X 和学生 Y 是否在同一组里。
若是则输出 Yes.，否则输出 No.。
【输入格式】
第一行输入 \(N\) 和 \(M\)。
接下来 \(N\) 行输入每一个同学的名字。
再往下 \(M\) 行每行输入两个名字，且保证这两个名字都在上面的 \(N\) 行中出现过，表示这两个参赛选手在同一个组里。
再来输入 \(K\)。
接下来输入 \(K\) 个体育老师的询问。
【输出格式】
对于每一个体育老师的询问，输出 Yes. 或 No.。
【样例输入】
10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra
【样例输出】
No.
Yes.
Yes.
解析
同样是一道map+并查集，但是这题让我意识到快读和关闭输入输出同步流是相冲突的，特别是在变量中含string型的情况，估计是cin>>string实际上是重载成getchar或者getline从而导致string型无法正常赋值。所以最好长长记性。真有string类就别手贱加个关闭输入输出同步流了。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
map<string,string>pre;
map<string,int>rk;
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
/*void init(int n){
for(int i=1;i<=n;i++){
pre[i]=i;
rk[i]=1;
}
}*/
/*int find(int x){
if(pre[x]==x) return x;
return find(pre[x]);
}*/
string find(string x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
bool issame(string x, string y)
{
// cout<<x<<" "<<y<<endl;
return find(x) == find(y);
}
bool join(string x,string y){
x=find(x);
y=find(y);
if(x==y) return false;
if(rk[x]>rk[y]) pre[y]=x;
else{
if(rk[x]==rk[y]) rk[y]++;
pre[x]=y;
}
return true;
}
int n,m,k;
signed main(){
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
string s,g;
n=read();m=read();
for(int i=1;i<=n;i++){
cin>>s;
// cout<<s<<endl;
pre[s]=s;
rk[s]=1;
}
while(m--){
cin>>s;
cin>>g;
join(s,g);
}
k=read();
while(k--){
cin>>s>>g;
//cout<<s<<" "<<g<<endl;
if(issame(s,g)) cout<<"Yes."<<endl;
else cout<<"No."<<endl;
}
}
板子五
村村通
题目描述
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？
【输入格式】
输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 \(n\) 和道路数目 \(m\) ；随后的 \(m\) 行对应 \(m\) 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 \(1\) 到 \(n\) 编号。
注意：两个城市间可以有多条道路相通。
在输入数据的最后，为一行一个整数 \(0\)，代表测试数据的结尾。
【输出格式】
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
【样例输入】
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
【样例输出】
1
0
2
998
【数据规模与约定】
对于 \(100\%\) 的数据，保证 \(1 \le n < 1000\) 。
解析
就合并完成工作完成后再循环一遍村庄看谁还没合并就行。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=1e6;
int pre[maxn],rk[maxn];
inline int read()//快读
{
int num=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num*w;
}
void init(int n){
for(int i=1;i<=n;i++){
pre[i]=i;
rk[i]=1;
}
}
/*int find(int x){
if(pre[x]==x) return x;
return find(pre[x]);
}*/
int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}
bool join(int x,int y){
x=find(x);
y=find(y);
if(x==y) return false;
if(rk[x]>rk[y]) pre[y]=x;
else{
if(rk[x]==rk[y]) rk[y]++;
pre[x]=y;
}
return true;
}
int jud(int n){
int num=0;
for(int i=1;i<=n;i++) if(pre[i]==i) num++;
return num-1;
}
int n,m;
signed main(){
while(n=read()){
int ans=0;
init(n);
m=read();
while(m--) join(read(),read());
cout<<jud(n)<<endl;
}
}