dominator tree

dominator_tree.cpp

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]);
		}
	}
};

dominatorTree.cpp

class dominatorTree{
	int n, dfnCnt;
	vector<vector<int>> G, rG, semiTree;
	vector<int> dfn, id, pa, semi, idom;
	vector<int> unionFind, best;
	int find(int x){
		if( x==unionFind[x] ) return x;
		int tmp = find(unionFind[x]);
		if( dfn[semi[best[x]]] > dfn[semi[best[unionFind[x]]]] )
			best[x] = best[unionFind[x]];
		return unionFind[x] = tmp;
	}
	void dfs(int u){
		id[ dfn[u] = ++dfnCnt ] = u;
		for(int v: G[u]){
			if(dfn[v]) continue;
			pa[v] = u, dfs(v);
		}
	}
public:
	void init(int _n){
		n = _n;
		G.clear(), G.resize(n+1);
		rG.clear(), rG.resize(n+1);
	}
	void addEdge(int u,int v){
		G[u].emplace_back(v);
		rG[v].emplace_back(u);
	}
	vector<vector<int>> buildTree(int root){
		dfnCnt = 0;
		semiTree = vector<vector<int>>(n+1);
		dfn = id = pa = semi = idom = vector<int>(n+1);
		iota(semi.begin(), semi.end(), 0);
		unionFind = best = semi;
		dfs(root);
		for(int i = dfnCnt; i>1; --i){
			int u = id[i];
			for(int v: rG[u]) if(dfn[v]){
				find(v);
				if( dfn[semi[u]] > dfn[semi[best[v]]] )
					semi[u] = semi[best[v]];
			}
			semiTree[semi[u]].emplace_back(u);
			unionFind[u] = pa[u];
			for(int w: semiTree[pa[u]]){
				find(w);
				if(semi[best[w]]==pa[u]) idom[w] = pa[u];
				else idom[w] = best[w];
			}
			semiTree[pa[u]].clear();
		}
		vector<vector<int>> tree(n+1);
		for(int i = 2; i<=dfnCnt; ++i){
			int u = id[i];
			if(idom[u]!=semi[u]) idom[u] = idom[idom[u]];
			tree[idom[u]].emplace_back(u);
		}
		return tree;
	}
};