题解 P11674 [USACO25JAN] Reachable Pairs G

cjh20090318 · 2025-02-04 09:29:31 · 题解

Gold 组唯一过的一道题。

题意

参见题目描述。

分析

移除节点并不方便维护连通性，考虑倒序添加用并查集维护。

考虑移除这两点操作的本质是什么。

所有 s_t = 0 的情况是比较好做的，直接加边即可。

在开始询问以前只需要添加连接两个虚点的边即可。

使用按秩合并和路径压缩并查集维护总点数和实点数，时间复杂度 O(N+M)。

代码

//the code is from chenjh
#include<cstdio>
#include<vector>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m;
bool s[MAXN],vis[MAXN];
vector<int> G[MAXN];
struct dsu{
    int fa[MAXN],sz[MAXN],z[MAXN];
    void init(){*fa=*sz=*z=0;for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1,z[i]=0;}
    int find(const int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    int size(const int x){return z[find(x)];}//当前连通块实点个数。
    void add(const int x){++z[find(x)];}//连通块添加一个实点。
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y]) swap(x,y);
        fa[y]=x,sz[x]+=sz[y],z[x]+=z[y];
    }
    bool same(const int x,const int y){return find(x)==find(y);}
}S;
LL ans[MAXN];
int main(){
    scanf("%d%d ",&n,&m),S.init();
    for(int i=1;i<=n;i++) s[i]=getchar()^'0';
    for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int u=1;u<=n;u++)if(s[u])for(const int v:G[u])if(s[v]) S.merge(u,v);//两个都为虚点，合并。
    LL now=0;
    for(int u=n;u>0;--u){
        if(s[u]){
            int z=S.size(u);
            now-=z*(z-1ll)/2,S.add(u),now+=z*(z+1ll)/2;
        }
        else{
            for(const int v:G[u])if((s[v]||v>u)&&!vis[S.find(v)]){
                int z=S.size(v);
                now-=z*(z-1ll)/2;
                vis[S.find(v)]=1;//删除每个连通块原来贡献的答案，标记防止重复。
            }
            S.add(u);
            for(const int v:G[u])if(s[v]||v>u)S.merge(u,v),vis[S.find(v)]=0;//连通。
            int z=S.size(u);
            now+=z*(z-1ll)/2;//更新答案。
        }
        ans[u]=now;
    }
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}