P10378 [GESP202403 七级] 交流问题 题解

· · 题解

看楼下没有一位DaLao用并查集写的，本蒟蒻瑟瑟发抖地水了这篇题解。

思路：

  1. 快读。
  2. 建关系（可参考P1892，A 与 B+N，B 与 A+N）。
  3. 加大小，权值（>N的数的个数）。
  4. 遍历每个集团，把两种数小的加入minn，大的加入maxx（分大于小于N）.
  5. 输出。

    代码:

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mod 998244353
#define ll long long
using namespace std;
ll n,m,u,v,minn,maxx;
struct bcj{                    //并查集
    int len;                   //长度
    int q[200005];             //存储，q[i]代表i的老大
    int si[200005];            //老大团大小（只取顶级老大）
    int pi[200005];
    void init(int lenn){       //初始化一个长度为lenn的并查集
        len=lenn;
        for(int i=1;i<=len;i++)
            pi[i]=0;
        for(int i=len+1;i<=len*2;i++)
            pi[i]=1;
        for(int i=1;i<=len*2;i++)
            q[i]=i,si[i]=1;
    }
    int Find(int t){           //找t的顶级老大
        if(q[t]!=t) q[t]=Find(q[t]);
        return q[t];
    }
    bool same(int a,int b){    //a和b是否在一个集合中
        int a_1=Find(a),b_1=Find(b);
        return a_1==b_1;
    }
    void add(int a,int b){     //合并a和b所在老大团
        if(same(a,b)) return ;
        int a_1=Find(a),b_1=Find(b);
        q[a_1]=b_1;
        q[a]=b_1;
        si[b_1]+=si[a_1];
        pi[b_1]+=pi[a_1];
    }
    int num(){                 //求老大团数
        int ans=0;
        for(int i=1;i<=len;i++)
            if(q[i]==i)
                ans++;
        return ans;
    }
    int siz(int a){
        return si[a];
    }
    int piz(int a){
        return pi[a];
    }
}a;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int main(){
    n=read();m=read();
    a.init(n);
    for(int i=1;i<=m;i++){
        u=read();v=read();
        a.add(u,v+n);
        a.add(u+n,v);
    }
    for(int i=1;i<=n*2;i++){
        if(a.Find(i)==i){
//          cout<<a.piz(i)<<' '<<a.siz(i)<<endl;
            minn+=min(a.piz(i),a.siz(i)-a.piz(i));
            maxx+=max(a.piz(i),a.siz(i)-a.piz(i));
        }
    }
    minn/=2;
    maxx/=2;
    printf("%lld %lld",minn,maxx);

    return 0;
}

码风不好，还请见谅。