并查集的基础题

## 洛谷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;
}
```