支配树

notes

概述

对于有向图 $G=(V,E)$，在给定源点 $s \in V$（$s$ 可达 $V$ 中其他节点）的情况下，若任意 $s \to y$ 的路径都经过 $x$，则称 $x$ 支配 $y$，$x$ 是 $y$ 的支配点，记作 $x=dom_y$。支配关系满足传递性、自反性、反对称性，是偏序关系，偏序关系可以用 DAG 刻画。

支配关系还满足若 $x = dom_z,y = dom_z$ 则 $x=dom_y$ 或 $y = dom_x$。满足这个性质的偏序关系可以用树刻画。记 $idom_x$ 为 $x$ 的直接支配点（不为 $x$），满足若 $y=dom_x,y \ne x$ 那么 $y=dom_{idom_x}$，直观理解就是支配点中离 $x$ 最近的那个。$idom_x \to x$ 可以得到一棵树，称为支配树。

DAG

求解 DAG 的支配树，有一个简单的算法。

拓扑排序，按拓扑序从小到大求解。对于点 $x$，DAG 上以其为终点的边有 $(s_1,x),(s_2,x)…$，则其直接支配点为 $LCA(s_1,s_2,…)$。

需要添加叶子节点求 LCA，用倍增求解，时间复杂度 $O((n+m)\log n)$。

一般图

先求出 dfs 树，$x<y$ 当且仅当 $dfn_x<dfn_y$，记 $[x,y]$ 为树上 $x$ 到 $y$ 路径上的点（$(x,y)$ 同理）。

引理 1 $idom_u$ 是 $u$ 的真祖先（不含 $u$ 的祖先）。

证明显然。

记 $lca$ 为 $lca(u,v)$。

引理 2 若 $u < v$，那么任意 $u$ 到 $v$ 的路径一定经过 $lca$ 的祖先。

横叉边满足从大到小，可以感性理解。

那么一定存在祖先节点使得其可以通过大于 $x$ 的节点到达 $x$，记为 $y$，而 $(y,x)$ 都不能作为 $idom_x$。只需要考虑满足该性质的最小的祖先即可。

半支配点 存在路径 $y \to p_1 \to p_2 \to … \to x,p_i > x$ 的最小的 $x$ 的祖先 $y$ 称为 $x$ 的半支配点，记作 $sdom_x$。

考虑通过半支配点求得直接支配点。记 $p_x$ 为 $(sdom_x,x)$ 上 $sdom$ 最小的点，有

考虑将 $idom_x$ 的求解挂在 $sdom_x$ 上。遍历 dfs 树，用带权并查集维护每个点到当前节点 $sdom$ 最小的点，直接查询即可。最后按 $dfs$ 序从大到小计算 $idom$。时间复杂度 $O(n \log n)$。

考虑求解半支配点。设求解 $sdom_x$，分类讨论

  • 对于树边或前向边 $y \to x$，用 $y$ 更新 $sdom_x$。

  • 对于中间有点的路径，枚举 $y \to x$ 作为最后一条边。

    直接用 $sdom_y$ 更新是不对的，因为 $sdom_x$ 到 $x$ 可能存在点 $p$ 满足 $x < p < y$。

    记 $z$ 为 $sdom_x$ 到 $x$ 上最小的点，根据引理 2，$z$ 一定是 $y$ 的祖先。只需考虑 $z$ 在 $[lca(x,y),y)$ 上的情况即可，否则可以通过树边到达 $x$。用 $sdom_z$ 更新 $sdom_x$ 即可。

    实现与求解直接支配点相同，用一个并查集即可，具体见代码。

时间复杂度 $O(n \log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int n,m;
vector<int> G[N],FG[N],TG[N],vc[N];

int dfn[N],d_c=0,fdfn[N],vis[N],sdom[N],idom[N],pos[N],siz[N];     
void dfs(int u,int fu){ fdfn[dfn[u]=++d_c]=u,vis[u]=1; for(int v:G[u]) if(!vis[v]) dfs(v,u),TG[u].pb(v); }

struct DSU{
    int fa[N],mn[N];
    void init(int n){ for(int i=1;i<=n;++i) fa[i]=i,mn[i]=i; }
    int find(int x){
        if(x==fa[x]) return x; int res=find(fa[x]);
        if(dfn[sdom[mn[fa[x]]]]<dfn[sdom[mn[x]]]) mn[x]=mn[fa[x]];
        return fa[x]=res;
    }
}D;

void sol(int u){
    dfn[sdom[u]]=INF;
    for(int v:FG[u]){
        if(dfn[v]<dfn[u]){ if(dfn[v]<dfn[sdom[u]]) sdom[u]=v; }
        else{ D.find(v); if(dfn[sdom[D.mn[v]]]<dfn[sdom[u]]) sdom[u]=sdom[D.mn[v]]; }
    }
    vc[sdom[u]].pb(u);
    for(int v:vc[u]) D.find(v),pos[v]=D.mn[v];
    for(int v:TG[u]) D.fa[v]=u; 
}

int main(){

    n=rd,m=rd,D.init(n);
    for(int i=1,x,y;i<=m;++i) G[x=rd].pb(y=rd),FG[y].pb(x);

    dfs(1,0); for(int i=n;i>=1;--i) sol(fdfn[i]);
    for(int i=2;i<=n;++i){
        if(pos[fdfn[i]]==fdfn[i]) idom[fdfn[i]]=sdom[fdfn[i]];
        else idom[fdfn[i]]=idom[pos[fdfn[i]]];
    }

    return 0;
}

应用

1.点集的支配点

求点集在支配树上的 LCA 即可。

2.支配边

显然可以可以对每条边建立虚点。但此方法常数较大，有常数更小的做法。

引理 3 $(u,v)$ 是点 $x$ 的支配边当且仅当 $u,v$ 都是 $x$ 的支配点且 $u$ 到 $v$ 只有一条简单路径。

证明显然。

支配边显然是树边，对于树边 $(u,v)$，若 $u=idom_v$ 且 $u$ 到 $v$ 只有一条简单路径，那么 $(u,v)$ 支配 $v$ 支配的所有点。

对于树边 $(u,v)$ 且 $u=idom_v$，$u$ 到 $v$ 只有一条简单路径当且仅当计算 $sdom_v$ 时只有一种情况使得 $sdom=u$（注意重边）。

3.有向图的割点和割边

类似无向图，有向图的割点和割边为删去后强连通分量增加的点和边，称为强割点和强割边。

可以对每个强连通分量分别考虑，因此以下讨论均基于强连通图。

引理 4.1 点 $x$ 是强割点当且仅当对于任意 $u \ne x$，都存在点 $v \ne x$，使得以下之一成立：

  • 任意 $u$ 到 $v$ 的路径都经过 $x$。
  • 任意 $v$ 到 $u$ 的路径都经过 $x$。

引理 4.2 边 $(x,y)$ 是强割边当且仅当对于任意 $u$ 都存在点 $v$ 使得以下之一成立：

  • 任意 $u$ 到 $v$ 的路径都经过边 $(x,y)$。
  • 任意 $v$ 到 $u$ 的路径都经过边 $(x,y)$。

证明显然。

记 $DT(G,s)$ 为图 $G$ 以 $s$ 为源点的支配树。

任取一点 $s$，并判断它是否为强割点。根据条件 1，$DT(G,s)$ 除 $s$ 外的非叶子节点都是强割点，根据条件 2，$DT(G^{-1},s)$ 除 $s$ 外的非叶子节点都是强割点。

强割边判断同支配边。

例题

1.Team Rocket Rises Again

先求最短路 DAG，再求支配树即可。

2.[省选联考 2021 A 卷] 支配

先求支配树，只需判断是否存在 $1 \leadsto x \to y \leadsto p$ 且不经过 $idom_p$ 的路径即可，时间复杂度 $O(n^2+nq)$。

3.【R1-B】地铁线路

求强割边。

参考

《浅谈支配树及其应用》