【题解】P7520 [省选联考 2021 A 卷] 支配
LinkyChristian
·
·
题解
每周文章计划2021.12 第四周（3）
看到很多题解里有出现支配集和受支配集含糊混用的问题，因此撰此挫作带来更清晰的描述。
题目已经将受支配集的定义讲的很清楚了，这里我们更新一下这个定义：一个点的受支配集为除自己之外支配自己的点。
接下来构造支配树。
定义支配树是由一个点与它的受支配集中受支配集最大的那个点作为父亲连边所构成的树。
本道题可以 O (n^2) 地建立支配树，我们采取最简单粗暴的方法：对于每个点，求出删掉这个点后从 1 还能到达哪些点，不能到达的点就属于它的支配集，之后根据定义建树。
一条很好发现的引理：一个点的受支配集改变后，它在支配树上的子树里的所有点的受支配集也会改变。
因此即使加入一条边可能会改变多个点的受支配集，但我们只要考虑这些点中深度最浅的就可以了。
考虑受支配集改变的深度最浅的那一些点，那么一定是它的父亲不再支配它了（否则的话它的父亲也受到了改变，且深度比它更浅，与原定义不符）。我们做两遍 dfs ,对于每个询问：u -> v 求出 u 是否能到 fa_j , v 是否
能在去掉 fa_j 的情况下到达 j ,如果符合条件，说明 u -> v 这条边可以绕开 fa_j 从 1 到达 j ，那么此时 j 以及 j 的子树内所有点的受支配集改变。
上代码
```
#include<bits/stdc++.h>
#define N 6010
using namespace std;
int n,m,Q;
pair<int,int> q[20010];
int cnt,head[N],to[N],nxt[N];
int vis[N][N];
vector<int> ctrl[N];//受支配集
void insert(int u,int v) {
cnt++;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void dfs1(int now,int fr/*删掉的点*/) {
vis[now][fr]=1;
if(now==fr) return ;
for(int i=head[now]; i; i=nxt[i])
if(!vis[to[i]][fr]) dfs1(to[i],fr);
}
int id[N],fa[N];
bool cmp(int a1,int a2) {
return ctrl[a1].size()<ctrl[a2].size();
}
void build() {//建树
dfs1(1,0);
for(int i=1; i<=n; i++) {
dfs1(1,i),id[i]=i;//删掉i
for(int j=1; j<=n; j++)
if(vis[j][0]&&!vis[j][i]) ctrl[j].push_back(i);
//本来可以到达删除i后无法到达，说明j受i支配
}
sort(id+1,id+n+1,cmp);
for(int i=1; i<=n; i++) {
for(int j=0; j<ctrl[i].size(); j++) {
int v=ctrl[i][j];
if(ctrl[v].size()==ctrl[i].size()-1) {
fa[i]=v;
break;
//自己的受支配集里受除了其本身外的所有成员支配的即为自己的父亲
}
}
}
}
int U[N],V[N],vis2[N][N];
int Cg[N];//受支配集是否改变
void dfs2(int now,int fr,int del) {
if(now==del) return ;
vis2[now][fr]=1;
for(int i=head[now]; i; i=nxt[i])
if(!vis2[to[i]][fr]) dfs2(to[i],fr,del);
}
void calc() {
for(int i=2; i<=n; i++) dfs2(i,i,fa[i]);
//排除自己在支配树上的父亲后能到达哪些点
for(int i=1; i<=Q; i++) {
int ans=0,u=q[i].first,v=q[i].second;
for(int j=1; j<=n; j++)
if(vis[u][fa[j]]&&vis2[v][j]&&fa[j]!=1&&fa[j]!=u) Cg[j]=1;
//如果u在正图上能到达父亲，v在反图上能到达j，那么自己就被支配
for(int j=1; j<=n; j++) if(Cg[fa[id[j]]]) Cg[id[j]]=1;
//如果一个点的受支配集变了，那么其子树中的受支配集也会变
for(int j=1; j<=n; j++) if(Cg[j]) ans++,Cg[j]=0;
cout<<ans<<endl;
}
}
int main()
{
n=read(),m=read(),Q=read();
for(int i=1; i<=m; i++) {
U[i]=read(),V[i]=read();
insert(U[i],V[i]);
}
for(int i=1; i<=Q; i++) q[i].first=read(),q[i].second=read();
build();
cnt=0;memset(head,0,sizeof(head));
for(int i=1; i<=m; i++) insert(V[i],U[i]);//接下来是反图
calc();
return 0;
}
```