发布时间：2025-05-22

支配树

在有向无环图中，定义$x$是$k$的支配点，当删除$x$无法到达$k$，定义$idom(u)$为$u$的直接支配点，$idom(u) \rightarrow u$就是支配树

半支配点：一个$dfs$序最小的点$x$，可以通过一条路径从$x$到$u$，且经过的端点中，$dfn_v \gt dfn_u$

struct DominatorTree{
    // 支配树上：idm[u]->u
	vector<int> dfn,pos,sdm,idm,par,mn,fth;
	int dfc,n;
	vector<vector<int>> adj[3];
	DominatorTree(){}
	DominatorTree(int n){
		init(n);
	}
	void init(int n){
		dfn.resize(n+1);
		pos.resize(n+1);
		sdm.resize(n+1);
		idm.resize(n+1);
		par.resize(n+1);
		mn.resize(n+1);
		fth.resize(n+1);
		for(int i=0;i<3;i++)adj[i].assign(n+1,{});
		dfc=0;
		this->n=n;
	}
	void addEdge(int u,int v,int t){
		adj[t][u].push_back(v);
	}
	void addEdge(int u,int v){
		addEdge(u,v,0);
		addEdge(v,u,1);
	}
	void dfs(int u){
		dfn[u]=++dfc;
		pos[dfc]=u;
		for(auto v:adj[0][u]){
			if(!dfn[v]){
				dfs(v);
				fth[v]=u;
			}
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		int tmp=par[x];
		par[x]=find(par[x]);
		if(dfn[sdm[mn[tmp]]]<dfn[sdm[mn[x]]]){
			mn[x]=mn[tmp];
		}
		return par[x];
	}
	void tarjan(int st){
		dfs(st);
		for(int i=1;i<=n;i++)mn[i]=par[i]=sdm[i]=i;
		for(int i=dfc;i>=2;i--){
			int u=pos[i],res=INF;
			for(auto v:adj[1][u]){
				if(!dfn[v])continue;
				find(v);
				if(dfn[v]<dfn[u])res=min(res,dfn[v]);
				else res=min(res,dfn[sdm[mn[v]]]);
			}
			sdm[u]=pos[res];
			par[u]=fth[u];
			addEdge(sdm[u],u,2);
			u=fth[u];
			for(auto v:adj[2][u]){
				find(v);
				if(u==sdm[mn[v]])idm[v]=u;
				else idm[v]=mn[v];
			}
			adj[2][u].clear();
		}
		for(int i=2;i<=dfc;i++){
			int u=pos[i];
			if(idm[u]!=sdm[u])idm[u]=idm[idm[u]];
		}
	}
};

最短路有关

给定一个带权无向图，询问删去一个节点最多有多少条最短路发生变化

求出最短路径DAG，然后支配树即可