【CF2060E Graph Composition】题解

· · 题解

闲话

不知道为什么，这场 CF 我觉得 D 不可做，但是 E 很可做。（哦因为我太菜了）

思路

这道题要求通过增、删 F 中的边使得在 F 中存在从 u 到 v 的路径，当且仅当在 G 中存在从 u 到 v 的路径，即 F 的每个连通块形成的集合同等于 G 每个连通块所形成的集合。

先考虑删边。很显然，如果 F 中一条边连接的两个点在 G 中不属于同一个连通块，那么这条边显然必须删掉，反之不用。

然后删完边，考虑加边。这个时候 F 的每一个连通块所形成的集合肯定是 G 的某一连通块所形成的集合的子集。只需要将分散的 F 连通块连接成 G 的连通块。此时需要加的边的数量必然是 F 和 G 连通块数量的差。

代码

实现需要两个并查集。这里连边时如果是将原本不属于同意连通块的点连接，则返回 1，反之返回 0，以此计算连通块数目。

fa 数组：点在并查集中的父亲。

rt 函数：点在并查集中的根。

unite 函数：连接两个点。

join 函数：判断两个点是否在同一个连通块内。

#include<bits/stdc++.h>
#define ll long long 
#define pb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
//#define 
using namespace std;
int t;
int n,m1,m2,fa1[200005],fa2[200005],u[200005],v[200005];
int rt1(int x){return x==fa1[x]?x:fa1[x]=rt1(fa1[x]);}
int rt2(int x){return x==fa2[x]?x:fa2[x]=rt2(fa2[x]);}
int unite1(int x,int y){
    int fax=rt1(x),fay=rt1(y);
    if(fax!=fay){
        fa1[fax]=fay;
        return 1;
    }
    return 0;
}
int join1(int x,int y){
    int fax=rt1(x),fay=rt1(y);
    if(fax!=fay){
//      fa1[fax]=fay;
        return 0;
    }
    return 1;
}
int unite2(int x,int y){
    int fax=rt2(x),fay=rt2(y);
    if(fax!=fay){
        fa2[fax]=fay;
        return 1;
    }
    return 0;
}
int join2(int x,int y){
    int fax=rt2(x),fay=rt2(y);
    if(fax!=fay){
        return 0;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  t=1;
    cin>>t;
    while(t--){
        cin>>n>>m1>>m2;
        for(int i=1;i<=n;i++)fa1[i]=fa2[i]=i;
        int cnt1=n,cnt2=n;
        for(int i=1;i<=m1;i++)cin>>u[i]>>v[i];
        for(int i=1;i<=m2;i++){
            int x,y;cin>>x>>y;
            cnt2-=unite2(x,y);
        }
        int ans=0;
        for(int i=1;i<=m1;i++){
            int flag2=join2(u[i],v[i]);
//          cout<<i<<":"<<flag1<<" "<<flag2<<"\n";
            if(flag2==0)ans++;
            else cnt1-=unite1(u[i],v[i]);
        } 
//      cout<<cnt1<<" "<<cnt2<<" ";
        ans+=cnt1-cnt2;
        cout<<ans<<"\n";
    }
    return 0;
}