$n$ 个点 $m$ 条边的无向图，按编号从小到大依次删点，每次删点后将其邻点补成完全图，求新增边数。
$1 \le n,m \le 2 \times 10^5$。
最后 $(i,j)(i < j)$ 有连边当且仅当原图存在 $i \to j$ 的路径使得路径上点（除 $j$ 外）的编号均 $\le i$。
考虑枚举 $i$ 统计上述点对的数量，最后减去 $m$ 即为答案。
按编号从小到大枚举 $i$，枚举过的点标 $1$，未枚举的标 $0$。那么 $j$ 的数量即为 $i$ 所在的 $1$ 连通块相邻的 $0$ 点的数量。
用并查集维护连通块，用 set 记录相邻的 $0$ 点。当枚举到 $i$ 时，先将相邻的 $0$ 点加入对应的 set，再与相邻的 $1$ 点合并，$j$ 的数量即为对应 set 的大小。启发式合并，时间复杂度 $O(n\log^2n)$。
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define U(x) ((int)x.size())
const int N=2e5+100;
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int n,m; ll ans=0;
vector<int> G[N];
int fa[N],siz[N]; set<int> s[N];
void init(){ for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1; }
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
void mer(int x,int y){
x=find(x),y=find(y); if(x==y) return;
if(siz[x]<siz[y]) swap(x,y);
fa[y]=x,siz[x]+=siz[y]; for(auto v:s[y]) s[x].insert(v);
}
int main(){
n=rd,m=rd,init();
for(int i=1,x,y;i<=m;++i) G[x=rd].pb(y=rd),G[y].pb(x);
for(int u=1;u<=n;++u){
for(int v:G[u]) if(v>u) s[u].insert(v);
for(int v:G[u]) if(v<u) mer(v,u);
if(s[find(u)].count(u)) s[find(u)].erase(u);
ans+=U(s[find(u)]);
}
printf("%lld\n", ans-m);
return 0;
}
|