[ dominator tree ] 有向圖的支配樹

dominator tree，中文名稱叫支配樹
給一張有向圖$G$，我們從其中一個點$r$出發到$y$的所有路徑中，一定會經過點$x$，就稱$x$是$y$的必經點；我們把距離$y$最近的必經點稱為最近必經點，記為$idom(y)$。
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$，那對於一個點$y$，$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。
注意code裡的$idom$跟我定義的不一樣
我是看這份講義的偽代碼寫出來的：

	struct dominator_tree{
	static const int MAXN=5005;
	int n;// 1-base
	vector<int> G[MAXN],rG[MAXN];//存圖和反向圖
	int pa[MAXN],dfn[MAXN],id[MAXN],dfnCnt;
	int semi[MAXN],idom[MAXN],best[MAXN];
	vector<int> tree[MAXN];//dominator_tree存這裡
	void init(int _n){
	n=_n;
	for(int i=1;i<=n;++i)G[i].clear(),rG[i].clear();
	}
	void add_edge(int u,int v){
	G[u].push_back(v);
	rG[v].push_back(u);
	}
	void dfs(int u){
	id[dfn[u]=++dfnCnt]=u;
	for(auto v:G[u]) if(!dfn[v]){
	dfs(v),pa[dfn[v]]=dfn[u];
	}
	}
	int find(int y,int x){
	if(y<=x)return y;
	int tmp=find(pa[y],x);
	if(semi[best[y]]>semi[best[pa[y]]])
	best[y]=best[pa[y]];
	return pa[y]=tmp;
	}
	void tarjan(int root){
	dfnCnt=0;
	for(int i=1;i<=n;++i){
	dfn[i]=idom[i]=0;
	tree[i].clear();
	best[i]=semi[i]=i;
	}
	dfs(root);
	for(int i=dfnCnt;i>1;--i){
	int u=id[i];
	for(auto v:rG[u]) if(v=dfn[v]){
	find(v,i);
	semi[i]=min(semi[i],semi[best[v]]);
	}
	tree[semi[i]].push_back(i);
	for(auto v:tree[pa[i]]){
	find(v,pa[i]);
	idom[v] = semi[best[v]]==pa[i] ? pa[i] : best[v];
	}
	tree[pa[i]].clear();
	}
	for(int i=2; i<=dfnCnt; ++i){
	if(idom[i]!=semi[i]) idom[i]=idom[idom[i]];
	tree[id[idom[i]]].push_back(id[i]);
	}
	}
	};

view raw dominator_tree.cpp hosted with ❤ by GitHub