P8907 [USACO22DEC] Making Friends P 题解

模拟赛碰到这道题，花了 1.5h 场切了，讲一下我的思路。

首先你可以想到按题意模拟，时间复杂度 $\mathcal{O}(n^3)$ 可以获得 20pts。

发现 $(i,j)(i<j)$ 能连通的充要条件是存在一条 $i,j$ 之间的路径经过的所有点的编号 $\le i$。

删除一个点相当于把它的所有直接相连的点合并成一个连通块。

必要性：若不存在一条这样的路径那么每条路径都有至少一个点编号 $> i$，那在连通之前 $i$ 就会被删掉，不可能连通。

充分性：若存在这样一条路径那么 $i,j$ 一定会在删除前合并到同一个连通块。

我们考虑维护这样的 $j$，我们从小到大枚举 $i$,

然后将与 $i$ 相连的编号大于 $i$ 的点加入一个 set，将 set 与 $i$ 相连的编号小于 $i$ 的点的 set 进行启发式合并，最后 set 的大小就是满足 $(i,j)(i<j)$ 且存在一条 $i,j$ 之间的路径经过的所有点的编号 $\le i$ 的 $j$ 的数量，注意一定要删掉 $i$ 本身。时间复杂度 $\mathcal{O}(n\log^2 n)$

然后我考场上还在想只在枚举 $i$ 的时候删除 $i$ 的正确性，发现对于一个点 $k(k<i)$，set 里面有 $i$ 的一定是因为 $k$ 所在的连通块有一条与 $i$ 直接相连的边才被加入，然后因为有与 $i$ 直接相连的边所以一定会被合并到 $i$ 的 set 里，所以所有包含 $i$ 的 set 一定会被删除到，所以是正确的。

附上代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 2e5 + 10;
int n,m;
ll ans=0;
int fa[MAXN];
set<int>st[MAXN];
vector<int>G[MAXN];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return ;
	if(st[x].size()>st[y].size()) swap(x,y);
	fa[x]=y;
	for(int i:st[x]) st[y].insert(i);
	st[x].clear(); 
}
int main(){
//	freopen("friends.in","r",stdin);
//	freopen("friends.out","w",stdout);
	scanf("%d%d",&n,&m);
	FL(i,1,n) fa[i]=i;
	FL(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	FL(u,1,n){
		for(int v:G[u]) if(v>u) st[u].insert(v);
		for(int v:G[u]) if(v<u) merge(u,v);
		int id=find(u);
		if(st[id].find(u)!=st[id].end()) st[id].erase(u);
		ans+=st[id].size();
	}
	printf("%lld\n",ans-m);
}