有趣的 Joitter 交友[JOISC 2020 Day2]

发表于 2020-03-22 分类于 loj

题目链接

loj

题意

$n$ 个点的有向图， $m$ 次加边。对于每次加边后，求图经过尽可能多的转换后，图的边数。

一次转换为：选择三个不同的点 $x, y, z$ ，使得 $(x, y), (y, z), (z, y)$ 在当前的图中存在，那么在当前的图中，如果没有 $(x, z)$ 这一条边，则新加一条。

$n \leq 10^{5}$ 。

题解

JOI的题好毒瘤啊。。。不过看起来也不是很难？

考虑一个连通块，在这里两个点相连当且仅当他们之间两个方向的路径都存在。那么这个连通块中的点在转换后都会互相连了。因此一个块中，块内的点的贡献就是 $S i z e \times (S i z e - 1)$ 。

可以发现，如果两个块之间存在方向不同的两条边，那么就会合成一个块。

因此下面只需要考虑只单条路径的贡献，以及如何合并两个连通块。

思考一下发现，如果存在一条 $(x, y)$ 的路径，那么贡献就是 $S i z e_{y}$ 。有很多条连向 $y$ 的路径， $S i z e_{y}$ 就会被算多次。设集合 $v_{y}$ 表示有多少个点跟连通块 $y$ 中的点相连，那么贡献就是 $S i z e_{y} \times | v_{y} |$ 。

下面考虑合并两个连通块，假设这两个连通块是 $x, y$ ，且 $y$ 合并到 $x$ 中。

可以发现，合并之后：

1， $x, y$ 之间的边不能留，先删掉再说。

2，连接 $y$ 的点，会变成连 $x$ ，这时需要枚举连接 $y$ 的点。

3，连接 $y$ 的连通块，会变成连 $x$ ，这时需要枚举连接 $y$ 的连通块。

4，若存在另一个连通块 $u$ ，使得 $(u, x), (y, u)$ 或者 $(u, y), (x, u)$ 之间有连边，那么合并以后， $x + y$ 的连通块就会和 $u$ 之间有两个方向的边，而这样这两个连通块也会合并。因此还需记多一个 $y$ 连出去的连通块集合，然后递归处理。

综上，对于每个连通块 $x$ ，我们需要记录： $x$ 内的集合，连向 $x$ 的点的集合，连向 $x$ 的连通块集合，被 $x$ 连向的连通块集合。

合并的话启发式合并即可。

集合不需要比较大小，因此可用哈希表，直接上 unordered_set 就好了。

时间复杂度 $O (n \log n)$ ，假设 $n, m$ 同阶。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=100010;
int fa[N],siz[N];
int n;
ll ans;
unordered_set<int> v[N],g[N],t[N],s[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline ll calc(int x)
{
	return 1ll*siz[x]*(siz[x]-1+v[x].size());
}
inline void merge(int x,int y)
{
	ans-=calc(x)+calc(y);
	if(siz[x]+v[x].size()<siz[y]+v[y].size()) swap(x,y);
	vector<int> q;
	for(auto u:t[y]) if(t[u].count(x)) q.pb(u);
	for(auto u:g[y]) if(g[u].count(x)) q.pb(u);

	g[x].erase(y); g[y].erase(x);
	t[x].erase(y); t[y].erase(x);
	for(auto u:t[y]) t[x].insert(u),g[u].erase(y),g[u].insert(x);
	for(auto u:g[y]) g[x].insert(u),t[u].erase(y),t[u].insert(x);
	
	for(auto u:v[y]) if(find(u)!=x) v[x].insert(u);
	for(auto u:s[y]) if(v[x].count(u)) v[x].erase(u);
	for(auto u:s[y]) s[x].insert(u);

	siz[x]+=siz[y];
	fa[y]=x;
	ans+=calc(x);

	for(auto u:q) if(find(u)!=find(x)) merge(find(u),find(x));
}
inline void update(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	if(!v[fy].count(x)) v[fy].insert(x),ans+=siz[fy];//v
	if(t[fx].count(fy)) return;

	if(!t[fy].count(fx)) t[fx].insert(fy),g[fy].insert(fx);//t,g
	else merge(fx,fy);
}
int main()
{
	n=read();
	fo(i,1,n) fa[i]=i,siz[i]=1,s[i].insert(i);
	int x,y;
	CASET
	{
		x=read(),y=read();
		update(x,y);
		printf("%lld\n",ans);
	}
	return 0;
}