题解：P11674 [USACO25JAN] Reachable Pairs G

· · 题解

P11674 [USACO25JAN] Reachable Pairs G

题意：给定一张 n 点 m 边的无向图，从小到大删除每个节点及其所有邻边，如果 s_t=1 ，则删除节点后将其所有邻居两两连边。每次操作前输出可以互相到达的点对数。

由于题目中涉及删点操作，直接处理较为麻烦，因此考虑简化。

容易想到，删点的反向操作是加点，使用并查集即可简单维护，所以可以反向处理，从后往前依次加入图中节点并统计琪对答案的贡献。

进一步分析题目中的操作，可得：如果s_t=1, 则时刻t的操作不会对其余节点的连通性造成影响。

这样，题目中的两种操作分别转换为：

此时，在预处理时遇到 s_t=1 的节点时仍需暴力将其邻居两两连边，极端时间复杂度和空间复杂度均为 O( n^2 ) ，还需优化。

考虑定义一种节点，称为“虚点”。“虚点”是所有 s_t=1 的节点删除后的形态，正常参与连边，但本身不计入连通块大小，也不对答案产生贡献。这样，处理时就无需额外连边。加入“虚点”后，只需改变其所属连通块大小，并统计答案。这样在优化时间复杂度的同时还便于处理。

注意：由于“虚点”本身参与连边，因此在加点时连边不能跳过虚点。两个虚点之间的边应预先连接。

时间复杂度 O((n+m) \cdot α(n))

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,fa[200001],sz[200001],ans[200001];
vector<int>v[200001];
ll getfa(ll x){//并查集
    if(fa[x]==x)return x;
    return fa[x]=getfa(fa[x]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    string s;
    cin>>s;
    s='0'+s;//统一下标，方便处理
    for(int i=1;i<=n;i++)fa[i]=i;//并查集初始化
    for(int i=1;i<=m;i++){
        ll a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        if(s[a]=='1'&&s[b]=='1'){
            fa[getfa(a)]=getfa(b);
            //为确保连通性，预处理虚点连边
        }
    }
    ll jans=0;//当前答案
    for(int i=n;i>=1;i--){
        if(s[i]=='1'){
            //处理虚点
            ll jfa=getfa(i);
            jans+=sz[jfa];//贡献为其所在连通块大小
            sz[jfa]++;//加入虚点
            //不改变原图连通性
        }
        else{
            //处理普通点
            sz[i]=1;//初始化当前节点大小，方便计算
            for(int j=0;j<v[i].size();j++){
                if(v[i][j]<i&&s[v[i][j]]=='0')continue;
                //跳过未加入的普通点，后续加入时再处理
                ll fa_i=getfa(i),fa_to=getfa(v[i][j]);
                if(fa_i==fa_to)continue;
                //对答案贡献为待合并连通块中节点个数乘积（两两配对即可）
                jans+=sz[fa_i]*sz[fa_to];
                //合并连通块
                sz[fa_i]+=sz[fa_to];
                fa[fa_to]=fa_i;
            }
        }
        ans[i]=jans;//记录答案
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}