! JOISC2020DAY2有趣的 Joitter 交友

若是有双向连边，那么双向边连通的集合可视为一个集合，集合内的所有边都已连接，任何一个指向这其中一点的边相当于指向了所有点

但是并不是一个点指向另一个点就相当于它所在的集合指向了那个点

用并查集维护集合，\(set\)维护每个集合的出边和入边，启发式合并即可

注意，合并一次后有些边的加入也是子问题，递归合并即可

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=1e5+4;
int n,m,fa[N],siz[N];
long long ans;
set<int>in[N];
set<pair<int,int>>out[N];
#define fi first
#define se second 
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void add(int u,int v){
	int fu=find(u),fv=find(v),z;
	if(fu==fv||in[fv].find(u)!=in[fv].end())return;
	auto it=out[fv].lower_bound({fu,0});
	if(it==out[fv].end()||it->fi>fu){
		ans+=siz[fv];
		in[fv].insert(u);
		out[fu].emplace(fv,u);
		return;
	}
	vector<int>waitin;
	vector<pair<int,int>>waitout;
	if(in[fu].size()+out[fu].size()<in[fv].size()+out[fv].size())fu^=fv^=fu^=fv;
	for(auto i:out[fv]){
		in[i.fi].erase(i.se);
		ans-=siz[i.fi];
		if(i.fi!=fu)waitout.push_back(i);
	}
	out[fv].clear();
	ans+=2ll*siz[fu]*siz[fv]-1ll*siz[fv]*in[fv].size()+1ll*siz[fv]*in[fu].size();
	for(auto i:in[fv]){
		z=find(i);
		out[z].erase({fv,i});
		if(fu!=z)waitin.push_back(i);
	}
	in[fv].clear();
	fa[fv]=fu;
	siz[fu]+=siz[fv];
	for(auto i:waitin)add(i,fu);
	for(auto i:waitout)add(i.se,i.fi);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){fa[i]=i;siz[i]=1;}
	for(int i=1,u,v;i<=m;i++){
		u=read();v=read();
		add(u,v);
		cout<<ans<<"\n";
	}
	return (0-0);
}

! JOISC2020DAY2有趣的 Joitter 交友

原文：https://www.cnblogs.com/aurora2004/p/12555501.html