题解：CF2060E Graph Composition

lalaji2010 · 2025-01-23 14:06:34 · 题解

CF2060E Graph Composition

分析

题目的意思其实就是，求最小代价，使得图 F 与图 G 连通情况相同。

考虑必须做的操作。

那么 F 中使得与 G 连通情况不同的边必须删去。G 中有多余的边使得与 F 连通情况不同，则 F 必须加上这些边。完成这些操作后，F 图合法。

连通情况使用并查集维护即可。

由于这些操作都是必须做的，所以操作次数一定是最小的。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int t;
int n,m1,m2;
int f[200005],f1[200005],a[200005],b[200005],c[200005],d[200005];
int find(int k){
    if(f[k]==k){
        return f[k];
    }
    return f[k]=find(f[k]);
}
int find1(int k){
    if(f1[k]==k){
        return f1[k];
    }
    return f1[k]=find1(f1[k]);
}
int main(){
    cin>>t;
    while(t--){
        int cnt=0;
        cin>>n>>m1>>m2;
        for(int i=0;i<=n;i++) f[i]=i,f1[i]=i;
        for(int i=1;i<=m1;i++){
            int u,v;
            cin>>u>>v;
            a[i]=u,b[i]=v;
        }
        for(int i=1;i<=m2;i++){
            int u,v;
            cin>>u>>v;
            c[i]=u,d[i]=v;
            int fu=find(u),fv=find(v);
            if(fu==fv) continue;
            f[fv]=fu;
        }
        for(int i=1;i<=m1;i++){
            int u=a[i];
            int v=b[i];
            int fu=find(u),fv=find(v);
            int fu1=find1(u),fv1=find1(v);
            if(fu==fv&&fu1!=fv1){
                f1[fv1]=fu1;
            }else if(fu!=fv){
                cnt++;
            }
        }
        for(int i=1;i<=m2;i++){
            int u=c[i];
            int v=d[i];
            int fu=find(u),fv=find(v);
            int fu1=find1(u),fv1=find1(v);
            if(fu1!=fv1){
                f1[fv1]=fu1;
                cnt++;
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}