题意

给定一张

n

个点

m

条边的有向图

G

，对于任意两个点

u, v

，若从顶点

1

出发到达顶点

v

的所有路径都需要经过顶点

u

，则称顶点

u

支配顶点

v

。特别地，每个顶点支配其自身。

对于任意一个点

v

，我们将图中支配顶点

v

的顶点集合称为

v

的受支配集

D_v

。

现在有

q

次互相独立的询问，每次询问给出一条有向边，请你回答在图

G

中加入该条边后，有多少个顶点的受支配集发生了变化。

数据保证给出的图

G

中，从

1

号点出发能到达所有其他点，并且图中不包含重边与自环。

对于所有测试数据：

1 \le n \le 3 \times {10}^3

，

1 \le m \le 2 \times n

，

1 \le q \le 2 \times {10}^4

。

$O(n(n+m))$ 求受支配集

D_v=\sum_{u=1}^n [P(1,u,v)]

P(1,u,v)

表示从顶点

1

出发到达顶点

v

的所有路径都需要经过顶点

u

，即去掉

u

之后，从

1

出发将无法到达

v

。

考虑朴素求

D_v

，枚举一个

u

，dfs查看从

1

出发是否可以到

v

，如可以，则把

u

加入

D_v

。

这需要先枚举 $v$ ，再枚举 $u$ ，再dfs。
显然可以反过来，先枚举 $u$ ，再dfs，此时 $u$ 可以加入所有无法到达的点的受支配集。

求支配树

性质

传递关系：若 $x$ 支配 $y$ ， $y$ 支配 $z$ ，则 $x$ 支配 $z$ 。
链式关系：若 $x$ 支配 $a$ ， $y$ 也支配 $a$ ，则 $x,y$ 之间也存在支配关系。如不然则必定有一种情况，使得删除其中一个点后， $1$ 可从另一个点到达 $a$ 。

支配树

每个点与直接支配点（受支配集中距离自己最近的点）连边
$x$ 的支配集为支配树上所有 $x$ 的祖先。

构建支配树

方法1

x

的支配集中，

fa_x

是支配集大小最大的那个点。

方法2

类似于拓扑排序，把支配关系看作有向边，首先把

1

入队，然后重复进行如下操作：

取出队头 $u$ ，对于所有受支配集中存在点 $u$ 的点，把 $u$ 从受支配集中删掉。
对于所有没有入队并且受支配集中只剩下本身（支配集大小为 $1$ ）的点 $v$ 入队，连边 $(u,v)$ 。

求解

对于加入的每条边

(x\to y)

，点

v

的受支配集改变当且仅当：

$fa[v]$ 的受支配集改变；
或者 $fa[v]$ 不再支配 $v$

从

v

向上一直追溯，一定存在一个位置是第二种情况（存在一个

fa[v']

不再支配

v'

），则这个

v'

在支配树中的子树中的点都受影响。（可以dfn序上子树差分）

因此找到所有这样的

v'

即可。

这等价于考察加边

(x,y)

之后，每个点

v

的

fa

是否仍然支配它。对于点

v

：

找到路径 $1\to x\to y \to v$ ，其中 $1\to x,y\to v$ 都不经过 $fa[v]$ ；
$1\to x$ 不经过 $fa[v]$ 等价于： $x$ 不在 $fa[v]$ 的子树里。这可以利用dfn序直接判断）；
$y\to v$ $y \to v$ 不经过 $fa[v]$ $f a [v]$ 等价于：在反图上有 $v\to y$ $v \to y$ 不经过 $fa[v]$ $f a [v]$ 。
- 如果先枚举 $v$ ，再在反图上去掉 $fa[v]$ 后做dfs将复杂度巨大。
- 可以事先枚举 $v$ ，在反图上去掉 $fa[v]$ 后做dfs，能到的点都是 $y$ 。即把 $v$ 存到 $y$ 的邻接表 $adj[y]$ 中。

对每组询问

x,y

：

枚举 $v\in adj[y]$ ，查看 $1\rightarrow x$ 是否可以不经过 $fa[v]$ ，如可以，在 $v$ 的子树上打标记。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=3000+5;
vector<int> Adj[N],szpj[N],T[N],AdjT[N],Adj1[N];
int n,m,f[N];
bool vis[N],vis0[N];
void dfs(int u,int no){
	vis[u]=1;
	for(auto v:Adj[u]){
		if(vis[v]||v==no) continue;
		dfs(v,no);
	}
}

void dfs0(int u){
	vis0[u]=1;
	for(auto v:Adj[u]){
		if(vis0[v]) continue;
		dfs0(v);
	}
}
int sz[N],pre[N],t=0;
void dfsT(int u,int fa){
	sz[u]=1;
	pre[u]=++t;
	for(auto v:T[u]){
		if(v==fa) continue;
		dfsT(v,u);
		sz[u]+=sz[v];
	}
}
void dfs1(int u,int no,int U){
	if(u==no) return;
	vis[u]=1;
	Adj1[u].push_back(U);
	for(auto v:AdjT[u]){
		if(vis[v]||v==no) continue;
		dfs1(v,no,U);
	}
}
int c[N];
int main(){
	int q;
	cin>>n>>m;
	cin>>q;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		Adj[u].push_back(v);
		AdjT[v].push_back(u);
	}
	dfs0(1);
	// speical for node 1
	for(int i=1;i<=n;i++){
		szpj[i].push_back(1);
	}
	for(int i=2;i<=n;i++){
		memset(vis,0,sizeof vis);
		dfs(1,i);
		for(int j=1;j<=n;j++){
			if(vis0[j]&&vis[j]==0){
				szpj[j].push_back(i);
			}
		}
	}
	for(int i=2;i<=n;i++){
		int maxj=0;
		for(auto j:szpj[i]){
			if(j==i) continue;
			if(szpj[j].size()>szpj[maxj].size()) maxj=j;
		}
		T[maxj].push_back(i);
		f[i]=maxj;
	}
	dfsT(1,0);
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);
		dfs1(i,f[i],i);
	}
	for(int i=1;i<=q;i++){
		cin>>u>>v;
		memset(c,0,sizeof c);
		int ans=0;
		for(auto j:Adj1[v]){
			if(f[j]==0) continue;
			if(!(pre[u]>=pre[f[j]]&&pre[u]<pre[f[j]]+sz[f[j]])){
				c[pre[j]]++;
				c[pre[j]+sz[j]]--;
			}
		}
		for(int j=1;j<=n;j++) c[j]+=c[j-1];
		for(int j=1;j<=n;j++) ans+=!!c[j];
		cout<<ans<<"\n";
	}

	return 0;
}

P7520 [省选联考 2021 A 卷] 支配（题解）

文章操作

题意

$O(n(n+m))$ 求受支配集

求支配树

性质

支配树

构建支配树

方法1

方法2

求解

相关推荐

评论

P7520 [省选联考 2021 A 卷] 支配（题解）

文章操作

题意

O(n(n+m))O(n(n+m))O(n(n+m)) 求受支配集

求支配树

性质

支配树

构建支配树

方法1

方法2

求解

相关推荐

评论

$O(n(n+m))$ 求受支配集