支配树

2023-11-07 13:30:16

定义

对于一个有起点 \(s\) 的有向图，如果把点 \(a\) 和所有与 \(a\) 相连的边删掉，\(s\) 无法到达 \(b\)，那么称 \(a\) 支配 \(b\)，称 \(a\) 为 \(b\) 的支配点。

支配关系具有传递性：即若 \(a\) 支配 \(b\)，\(b\) 支配 \(c\)，那么 \(a\) 支配 \(c\)。

如果存在 \(a\) 支配 \(x\) 且 \(b\) 支配 \(x\)，\(a\neq b\)，一定存在 \(a\) 支配 \(b\) 或 \(b\) 支配 \(a\)。

所以说，支配关系可以构成一棵树，对于一个点，它支配它子树内的所有点，并且它的祖先都支配它。

DAG 的支配树

拓扑排序，那么一个点的支配点的拓扑序一定小于自己。按照拓扑序从小到大构建支配树，对于一个点 \(u\)，原图上能够到达它的点为 \(v_{i},v_2,\cdots ,v_k\)，那么需要有一个点同时支配 \(v_{i},v_2,\cdots ,v_k\)，即支配树上 \(v_{i},v_2,\cdots ,v_k\) 的 \(LCA\)。因为拓扑序的关系，拓扑序 \(<x\) 的所有点的支配树已经建好了，\(LCA\) 倍增即可。把 \(x\) 接到 \(LCA\) 的儿子上即可。

例题

P2597 [ZJOI2012]灾难

新建一个源点连向所有入度为 \(0\) 的点，然后跑支配树即可。

CF757F Team Rocket Rises Again

首先跑一遍 Dijkstra，对于一个点 \(x\)，对于所有 \(dis_x=dis_u+w_{u\to v}\) 的边，在新图上连边 \(u\to x\)，显然这个新图是一个 DAG，跑支配树即可。

普通有向图的支配树

Lengauer-Tarjan 算法

定义

首先找到原图的一棵 dfs 树，求出 dfs 序 \(dfn_u\)。

半支配点：一个点 \(u\) 的半支配点定义为：所有存在一条只经过 \(dfn_x>dfn_u\) （不含端点）的点 \(x\) 的路径，从 \(k\) 走到 \(x\)的点 \(k\) 中，\(dfn\) 最小的点。记为 \(semi_u\)。以下简称【存在一条只经过 \(dfn_x>dfn_u\) （不含端点）的点 \(x\)，从 \(k\) 走到 \(x\)】的点 \(k\) 为候选半支配点。只需要在所有候选半支配点里选 \(dfn\) 最小的一个即为支配点。

两个基本性质：

\(dfn_{semi_u}<dfn_u\)，因为显然 \(u\) 的父亲一定合法。
\(semi_u\) 一定是 \(u\) 在 \(dfs\) 树上的祖先。

如何求半支配点

考虑一条边 \(y\to x\)。

若 \(dfn_y<dfn_x\)：\(y\) 是 \(x\) 的候选半支配点。
若 \(dfn_y>dfn_x\)：那么 \(y\) 的所有 \(dfn_u>dfn_x\) 的祖先 \(u\) 的候选半支配点均是 \(x\) 的候选半支配点，我们只取里面最有用的，也就是 \(y\) 的所有 \(dfn_u>dfn_x\) 的祖先 \(u\) 的半支配点均是 \(x\) 的候选半支配点。

这两个条件是充要的。

考虑按照 \(dfn\) 序从大往小枚举点 \(u\)，枚举所有原图上能到达它的点 \(v\)（即反图上的出边），若 \(dfn_v<dfn_u\)，用 \(v\) 更新 \(semi_u\)；否则，设 \(l=LCA(u,v)\)，我们需要求出 \(l\) 到 \(v\) 的链上（不含 \(l\)）的点中 \(dfn\) 最小的 \(semi_k\) 。

由于是倒序枚举 \(dfn\)，此时 \(l\) 还未被加进来，而 \(l\) 到 \(v\) 的链上已经全都加进来了。采用带权并查集，每个点维护自己到根（已连通的部分的根）的所有点中，\(dfn_{semi_x}\) 最小的 \(x\) 是哪个。现在，询问 \(l\) 到 \(v\) 的链上（不含 \(l\)）的点中 \(dfn\) 最小的 \(semi_k\) 转化为询问并查集上到根的链的最小值，使用路径压缩做到 \(O(n\log n)\)，注意没有也不能按秩合并，所以复杂度不是 \(O(n\alpha(n))\)，不过常数很小，近似 \(O(n\alpha(n))\)。找到这个点 \(k\)，用 \(semi_k\) 更新 \(semi_u\) 即可。

inline int Min(int x,int y){return dfn[semi[x]]<dfn[semi[y]]?x:y;}
namespace dsu{
	int fa[N],val[N];
	int find_fa(int x){
		if(x==fa[x])return x;
		int f=fa[x];
		fa[x]=find_fa(fa[x]);
		val[x]=Min(val[x],val[f]);
		return fa[x];
	}
	inline int query(int x){
		find_fa(x);
		return val[x];
	}
}

求出 \(u\) 的 \(semi\) 之后，把 \(u\) 的儿子与 \(u\) 合并。

如何求支配点

显然需要用到刚才讲过的半支配点。

对于 \(u\) 和它的半支配点 \(semi_u\)，需要求出 \(semi_u\) 到 \(u\) 的链上（不含 \(semi_u\)）的所有点中，\(dfn_{semi_x}\) 最小的 \(x\)。

若 \(semi_x=semi_u\)，那么 \(u\) 的支配点就是 \(semi_u\)。
否则（显然只有可能 \(dfn_{semi_x}<dfn_{semi_u}\)），\(u\) 的支配点就是 \(x\) 的支配点。

现在我们要求的就是：\(semi_u\) 到 \(u\) 的链上（不含 \(semi_u\)）的所有点中，\(dfn_{semi_x}\) 最小的 \(x\)。这一部分和上面求半支配点中【求出 \(l\) 到 \(v\) 的链上（不含 \(l\)）的点中 \(dfn\) 最小的 \(semi_k\) 】很相似。

可以在求 \(semi\) 的时候同时求出支配点，也就是把求 \(x\) 的支配点时，要询问 \(semi_u\) 到 \(u\) 的链这部分，离线到求解 \(semi_u\) 的半支配点时。在这时，\(semi_u\) 到 \(u\) 的链（不含 \(semi_u\)）已经合并完了，询问 \(u\) 即可得到链上 \(dfn_{semi_x}\) 最小的 \(x\)，然后进行上面的讨论即可。

至此我们求出了支配点，也就求出了支配树，复杂度 \(O(n\log n)\)。

以下是 P5180 【模板】支配树的代码：

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*f;
}
const int N=2e5+5,M=3e5+5;
int n,m;
int dfn[N],semi[N],idom[N],node[N],inde;
inline int Min1(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline int Min(int x,int y){return dfn[semi[x]]<dfn[semi[y]]?x:y;}
namespace dsu{
	int fa[N],val[N];
	int find_fa(int x){
		if(x==fa[x])return x;
		int f=fa[x];
		fa[x]=find_fa(fa[x]);
		val[x]=Min(val[x],val[f]);
		return fa[x];
	}
	inline int query(int x){
		find_fa(x);
		return val[x];
	}
}
struct Edge{int to,next;};
struct Graph{
	Edge e[M];
	int head[N],ecnt;
	inline void adde(int u,int v){
		e[++ecnt]=(Edge){v,head[u]};head[u]=ecnt;
	}
	inline Edge& operator [](int x){return e[x];}
}e,e1,tr,e2;
#define pb push_back
void dfs1(int u){
	dfn[u]=++inde;node[inde]=u;
	for(int i=e.head[u],v;i;i=e[i].next)
		if(!dfn[v=e[i].to])dfs1(v),e2.adde(u,v);
}
int sz[N];
void dfs2(int u){
	sz[u]=1;
	for(int i=tr.head[u],v;i;i=tr[i].next)
		dfs2(v=tr[i].to),sz[u]+=sz[v];
}
int mn[N];
vector<int> buc[N];
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)mn[i]=i,semi[i]=i,dsu::val[i]=i,dsu::fa[i]=i;
	for(int i=1,u,v;i<=m;++i){
		u=read();v=read();
		e.adde(u,v);
		e1.adde(v,u);
	}
	dfs1(1);
	for(int i=n,u;i>=1;--i){
		u=node[i];
		for(int x:buc[u])mn[x]=dsu::query(x);
		for(int i=e1.head[u],v;i;i=e1[i].next){
			v=e1[i].to;
			if(dfn[v]<dfn[u])semi[u]=Min1(semi[u],v);
			else semi[u]=Min1(semi[u],semi[dsu::query(v)]);
		}
		for(int i=e2.head[u];i;i=e2[i].next)
			dsu::fa[e2[i].to]=u;
		buc[semi[u]].pb(u);
	}
	idom[1]=1;
	for(int i=2,u;i<=n;++i){
		u=node[i];
		if(semi[mn[u]]==semi[u])idom[u]=semi[u];
		else idom[u]=idom[mn[u]];
		tr.adde(idom[u],u);
	}
	dfs2(1);
	for(int i=1;i<=n;++i)printf("%d ",sz[i]);
	return 0;
}

码农公寓

定义