并查集 [修改数组,合根植物]
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
#include<bits/stdc++.h>
using namespace std;
const int N=1.1e6+10;
int sz[N];
int fina(int x){//状态压缩
if(sz[x]!=x){ //找父点
sz[x]=fina(sz[x]);
}
return sz[x];
}
int s,A[N],su;
int main()
{
for(int i=0;i<N;i++){ //并查集初始化
sz[i]=i;
}
cin>>s;
for(int i=0;i<s;i++){ //并查集初始化
cin>>su;
cout<<sz[fina(su)]<<" ";
sz[fina(su)]+=1;//把当前状态往后移一位标识当前点已经指向下一个父类
}
cout<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
//查找有多少个顶级父类
const int N=1e6+10;
int sz[N],m,n;
int ljys(int x){
if(sz[x]!=x){
int lj= ljys(sz[x]);
cout<<sz[x]<<" <- "<<lj<<" x:"<<x<<endl;
sz[x]=lj;
}
cout<<"x上:"<<x<<" "<<endl;
return sz[x];
}
int main()
{
int sum=0;
cin>>m>>n;
for(int i=1;i<=m*n;i++){
sz[i]=i;
}
int k,a,b;
cin>>k;
for(int i=1;i<=k;i++){
cin>>a>>b;
int a1=ljys(a);
int b1=ljys(b);
cout<<endl;
sz[ljys(a)]=ljys(b);
cout<<"x:"<<a1<<" <<-> "<<b1<<endl;
//状态转移
//sz[a]=ljys(b);//状态转移
for(int i=1;i<=m*n;i++){
cout<<i<<" ";
}
cout<<endl;
for(int i=1;i<=m*n;i++){
if(sz[i]==i){
sum++;
}
cout<<sz[i]<<" ";
}
cout<<endl;
}
// int sum=0;
// for(int i=1;i<=m*n;i++){
//
// if(sz[i]==i){
// sum++;
//}
//
//cout<<sz[i]<<" ";
//}
//cout<<endl<<sum;
//
return 0;
}
上面的讲的就是并查集 .蛮好的 ,嘿嘿