8.7第四周周三学习总结
1 并查集
1) 模板
板子
#include<bits/stdc++.h>
using namespace std;
void init()
{
for(int i=0; i<n; i++)
pre[i]=i;
}
int find(int a)
{
if(pre[a]==a)
//又写成单等了
return a;
else
return pre[a]=find(pre[a]);//记得是pre[a]=find(pre[a]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(a==b)
return;
else
pre[a]=b;
// pre[find(a)]=find(b);相当于这个
}
2） 习题
习题集1
习题集2（洛谷）
（1）不重复序列（并查集）
第一眼都不会想到用并查集解决
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e5+10;
int pre[maxn];
int a[maxn];
void init()
{
for(int i=0; i<maxn; i++)
pre[i]=i;
}
int find(int a)
{
if(pre[a]==a)
return a;
else
return pre[a]=find(pre[a]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(a==b)
return;
else
pre[a]=b;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
init();
/*
5
2 1 1 3 4
*/
for(int i=1; i<=n; i++)
{
int a;
cin>>a;
a=find(a);//找到a的祖先
cout<<a<<' ';
merge(a,a+1);//a+1为a的祖先
//自己写的一直超时，这个更巧妙
}
}
(2)排队询问人数（并查集应用）
错解
//(当成只维护集合大小的）（因为经过了路径压缩，每次都只会更新他的父亲的集合大小，不维护他的）
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=3e4+10;
int pre[maxn];
int a[maxn];
int num[maxn];
void init()
{
for(int i=0; i<maxn; i++)
{
pre[i]=i;
num[i]=1
};
}
int find(int a)
{
if(pre[a]==a)
return a;
else
return pre[a]=find(pre[a]);
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(a==b)
return;
else
{
pre[a]=b;
num[b]+=num[a];
这样只能维护集合大小4：1 2 3，8：5 6
//我们求不出来2到1 3
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
init();
int t;
while(t--)
{
char c;
int i,j;
cin>>c>>i>>j;
if(c=='M')
merge(i,j);
if(c=='C')
{
if(find(i)!=find(j))
cout<<"-1"<<endl;
else
{
cout<<abs(num[i]-num[j])<<endl;
}
}
}
}
正解（不太理解
#include<bits/stdc++.h>
using namespace std;
int fa[30001],front[30001],num[30001],x,y,i,j,n,T,ans; //fa[i]表示飞船i的祖先
//front[i]表示飞船i与其所在列队头的距离
//num[i]表示第i列的飞船数量
char ins;
int find(int n){ //查找祖先的函数
if(fa[n]==n)return fa[n];
int fn=find(fa[n]); //先递归找到祖先
front[n]+=front[fa[n]];
//终于懂了其实是在更新上一个m的，因为这个find在if外，每次都会执行
/*1：23 5： 678 传入3，时假设3的父亲是2，2祖宗是1，那么要先用2到队头去更新3到队头。
当时把1 23合并时只有2更新了
然后现在要1 23与 4 567合并*/
//不懂这一步
//在回溯的时候更新front（因为更新时要用到正确的front[祖先]，
//所以只能在回溯的时候更新）
return fa[n]=fn;
}
int main(){
cin>>T;
for(i=1;i<=30000;++i){ //定初值
fa[i]=i;
front[i]=0;
num[i]=1;
}
while(T--){
cin>>ins>>x>>y;
int fx=find(x); //fx为x所在列的队头
int fy=find(y); //fy同上
if(ins=='M'){
front[fx]=num[fy]; //x到队头的距离就是y的长度
//即加上y所在队列的长度
fa[fx]=fy; //将fy设为fx的祖先
num[fy]+=num[fx]; //更新以fy为队头队列的长度
num[fx]=0;
//以fx为队头的队列已不存在，更新
// find(x); find(y);
}
if(ins=='C'){
if(fx!=fy)cout<<"-1"<<endl; //若x和y的祖先不相同，则不在同一列
else cout<<abs(front[x]-front[y])-1<<endl; //否则利用x和y离队头的距离算
//出它们的距离
}
}
return 0;
}