题目链接
loj
题意
$n$ 个点的有向图，$m$ 次加边。对于每次加边后，求图经过尽可能多的转换后，图的边数。
一次转换为：选择三个不同的点 $x,y,z$，使得 $(x,y),(y,z),(z,y)$ 在当前的图中存在，那么在当前的图中，如果没有 $(x,z)$ 这一条边，则新加一条。
$n\leq 10^5$。
题解
JOI的题好毒瘤啊。。。不过看起来也不是很难？
考虑一个连通块，在这里两个点相连当且仅当他们之间两个方向的路径都存在。那么这个连通块中的点在转换后都会互相连了。因此一个块中，块内的点的贡献就是 $Size\times (Size-1)$。
可以发现，如果两个块之间存在方向不同的两条边，那么就会合成一个块。
因此下面只需要考虑只单条路径的贡献，以及如何合并两个连通块。
思考一下发现，如果存在一条 $(x,y)$ 的路径，那么贡献就是 $Size_y$。有很多条连向 $y$ 的路径，$Size_y$ 就会被算多次。设集合 $v_y$ 表示有多少个点跟连通块 $y$ 中的点相连，那么贡献就是 $Size_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$ 同阶。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #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];
if(t[fx].count(fy)) return;
if(!t[fy].count(fx)) t[fx].insert(fy),g[fy].insert(fx);
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;
}
|