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

#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;
}