题解：P11674 [USACO25JAN] Reachable Pairs G

题意：给定一张

n

点

m

边的无向图，从小到大删除每个节点及其所有邻边，如果

s_t=1

，则删除节点后将其所有邻居两两连边。每次操作前输出可以互相到达的点对数。

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

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

进一步分析题目中的操作，可得：如果

s_t=1

, 则时刻t的操作不会对其余节点的连通性造成影响。

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

$s_t=0$ ，加入该节点及其所有邻边，可能会合并多个连通块
$s_t=1$ ，将当前节点加入其所属连通块

此时，在预处理时遇到

s_t=1

的节点时仍需暴力将其邻居两两连边，极端时间复杂度和空间复杂度均为

O( n^2 )

，还需优化。

考虑定义一种节点，称为“虚点”。“虚点”是所有

s_t=1

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

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

时间复杂度

O((n+m) \cdot α(n))

代码：

CPP

#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;
}

题解：P11674 [USACO25JAN] Reachable Pairs G

文章操作

相关推荐

评论

题解：P11674 [USACO25JAN] Reachable Pairs G