定义

对于一个有起点 \(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\)。因为拓扑序的关系，拓扑序 \( 的所有点的支配树已经建好了，\(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}，因为显然 \(u\) 的父亲一定合法。
• \(semi_u\) 一定是 \(u\) 在 \(dfs\) 树上的祖先。

如何求 半支配点

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

• 若 \(dfn_y：\(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，用 \(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]]

#include 
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] 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]