P8907 [USACO22DEC] Making Friends P 题解

$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)。

#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); //此时 u 不是 0 点，如果有要删去。
        ans+=U(s[find(u)]);
    }

    printf("%lld\n", ans-m);

    return 0;
}