并查集的基础题
## 洛谷p1196 绿 35m
点到祖先的距离
代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int f[N],dist[N],num[N];//num计算祖先有多少儿子 ，dist计算距离祖先有几个
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else{
int k=f[x];
f[x]=zx(f[x]);
dist[x]+=dist[k];
num[x]=num[f[x]];
return f[x];
}
}
void h(int x,int y){
int r1=zx(x),r2=zx(y);
f[r1]=r2;
dist[r1]=dist[r2]+num[r2];
num[r2]+=num[r1];
num[r1]=num[r2];
}
int main(){
int n;cin>>n;
for(int i=1;i<=N;i++){
f[i]=i;
num[i]=1;
}
for(int i=1;i<=n;i++){
char x;cin>>x;
int a,b;cin>>a>>b;
if(x=='M'){
if(zx(a)!=zx(b)){
h(a,b);
}
}
else{
if(zx(a)==zx(b)){
cout<<abs(dist[a]-dist[b])-1<<endl;
}
else cout<<"-1"<<endl;
}
}
}
```
## 洛谷p1525 绿 30m
种类并查集（2种）
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int f[N];
struct A{
int x,y,val;
}a[N];
ll b[N];
bool cmp(A q,A w){
return q.val>w.val;
}
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。
}
void h(int x,int y){
f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
}
int main(){
ll n,m;cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].val;
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m+1;i++){
if(zx(a[i].x)==zx(a[i].y)){
cout<<a[i].val<<endl;
break;
}
else{
if(!b[a[i].x])b[a[i].x]=a[i].y;
else h(b[a[i].x],a[i].y);//与敌人的敌人合并
if(!b[a[i].y])b[a[i].y]=a[i].x;
else h(a[i].x,b[a[i].y]);
}
}
}
```
## 洛谷p2024 绿 35m
种类并查集（3种）
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int f[N];ll n,m;
ll ans=0;
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。
}
void h(int x,int y){
f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
f[zx(y+n)]=zx(x+n);
f[zx(y+n+n)]=zx(x+n+n);
}
void h1(int x,int y){
f[zx(y+n)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
f[zx(y+n+n)]=zx(x+n);
f[zx(y)]=zx(x+n+n);
}
int main(){
cin>>n>>m;
for(int i=1;i<=3*n;i++)f[i]=i;
while(m--){
int op,x,y;cin>>op>>x>>y;
if(x>n||y>n){
ans++;continue;
}
if(op==1){
if(zx(x+n)==zx(y)||zx(y+n)==zx(x))ans++;//y吃x，x吃y else{
else{
h(x,y);
}
}
else{
if(zx(x)==zx(y)||zx(y)==zx(x+n))ans++;//如果x和y是同类,y吃x
else{
h1(x,y);
}
}
}
cout<<ans<<endl;
}
## 洛谷p1197 绿 1h
先合并后摧毁
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
struct A{
int x,y,id;
}a[N];
ll n,m;
int f[N],num=0,ans[N],vis[N];
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。
}
void h(int x,int y){
if(zx(y)!=zx(x))num--;
f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
}
bool cmp(A q,A w){
return q.id<w.id;
}
int main(){
cin>>n>>m;num=n;
for(int i=0;i<n;i++)f[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y;
a[i].id=0;
}
int k;cin>>k;
for(int i=1;i<=k;i++){
int z;cin>>z;
vis[z]=k-i+1;//给下面k个数字逆着给个下标
}
for(int i=1;i<=m;i++){
a[i].id=max(vis[a[i].x],vis[a[i].y]);
}
sort(a+1,a+m+1,cmp);
int j=1;
for(int i=0,j=1;i<=k;i++){//枚举被攻占的星球序号
while(j<=m&&a[j].id==i){
h(a[j].x,a[j].y);
j++;
}
ans[i]=num-(k-i);
}
for(int i=k;i>=0;i--)cout<<ans[i]<<endl;
return 0;
}
```
## 洛谷p1640 蓝 1h
题意：lxh有n个武器，每个武器有两种属性，每个武器最多只能使用一次，要从属性1开始连续递增攻击，最多能连续攻击几次？
分析：问题当中要从小到大使用所有属性，所以肯定要有以1…10000属性为点的一侧。把装备放在另一侧，装备和它的两个属性连边.(也就相当于从左到右一连，再从右到左一连，才相当于用了两个属性。从小到大匹配属性点，因为题目要求必须要每个技能依次释放，所以要有else break环节，这是一个网络流二分图中需要重点注意的环节，有时要加而有时不要，这里要加上还是比较好理解的。
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<int>v[N];
int f[N],t=0,vis[N],l[N];
int zx(int x){
for(int i=0;i<v[x].size();i++){
int p=v[x][i];//x的序列们
if(vis[p]!=t){//如果上次访问的时间不是当前时间
vis[p]=t;//更新为当前时间
if(l[p]==0||zx(l[p])){//如果x没有匹配或有路径
l[p]=x;//p与x匹配
return 1;
}
}
}
return 0;
}
int main(){
ll n,a,b;cin>>n;
for(int i=1;i<=n;i++){
cin>>a>>b;
v[a].push_back(i);//将序列存入属性里
v[b].push_back(i);
}
int ans=0;
for(int i=1;i<=n;i++){
t++;
if(zx(i))ans++;//如果存在就加
else break;//不存在就结束 必须是连续的
}
cout<<ans<<endl;
return 0;
}
```
## 洛谷p1892 绿 10m
题意：朋友的朋友是朋友，敌人的敌人是朋友，求最多团体数。
分析：种类并查集（2种）
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int f[N];
struct A{
int x,y;
}a[N];
ll b[N];
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。
}
void h(int x,int y){
f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
}
int main(){
ll n,m;cin>>n>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
char op;cin>>op;
cin>>a[i].x>>a[i].y;
if(op=='E'){
if(!b[a[i].x])b[a[i].x]=a[i].y;
else h(b[a[i].x],a[i].y);//与敌人的敌人合并
if(!b[a[i].y])b[a[i].y]=a[i].x;
else h(a[i].x,b[a[i].y]);
}
else{
h(a[i].x,a[i].y);
}
}
map<int,int>mp;
int ans=0;
for(int i=1;i<=n;i++){
mp[zx(i)]++;
if(mp[zx(i)]==1)ans++;
}
cout<<ans<<endl;
}
```
## 洛谷p1621 绿 2h
题意：给了a到b范围内的整数，每次选择两个合并，这个两个拥有大于等于p的公共质因数，求最后有多少个集合
代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
vector<int> prime;
bool is_prime[N];
int f[N];int a,b,p,v[N];
int zx(int x){
if(f[x]==x)return x;//x没爸爸
else return f[x]=zx(f[x]);//找出爸爸的爸爸的。。
}
void h(int x,int y){
f[zx(y)]=zx(x);//x的最大祖先变成y最大祖先的爸爸；
}
void Eratosthenes(int n) {
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) is_prime[i] = true;
// i * i <= n 说明 i <= sqrt(n)
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i])
for (int j = i * i; j <= n; j += i) is_prime[j] = false;
}
for (int i = 2; i <= n; ++i)
if (is_prime[i]&&i>=p) prime.push_back(i);
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>a>>b>>p;
for(int i=1;i<=b;i++)f[i]=i;
Eratosthenes(b);
int cnt=1;
for(int i=p;i<=b;i++){
if(is_prime[i]){
v[cnt]=i;
cnt++;
}
}
for(int i=1;i<cnt;i++){
int c=0;
while(c*v[i]<a)c++;
while(v[i]*(c+1)<=b){
h(v[i]*c,v[i]*(c+1));
c++;
}
}
ll ans=0;
for(int i=a;i<=b;i++){
if(f[i]==i)ans++;
}
cout<<ans<<endl;
return 0;
}
```