先抛出一个问题:给一个有向图,问从 \(1\) 节点出发,求每个节点的受支配集。
这里,支配的定义为:若从 \(1\) 结点出发到 \(v\) 节点的所有路径中,都必须经过 \(u\) 节点,则称 \(u\) 支配 \(v\)。
那么受支配集意思就是对于 \(v\) 点满足条件的 \(u\) 点的集合。那么根据支配的定义,我们可以推出一个结论:如果 \(u_0\) 支配 \(v\),\(u_1\) 支配 \(v\),那么必有 \(u_0\) 支配 \(u_1\),或 \(u_1\) 支配 \(u_0\)。这是显然的, 因为如果它们两个点不互相支配的话,那这两个点都会存在另一条不经过自己并经过对方到达 \(v\) 的路径,并不能满足这两个点是 \(v\) 的支配点。
也就是说,这是一个树形结构。每个点的父亲为第一个支配他的点,那么这棵支配树中每个点的祖先和自己都是支配自己的点。现在,我们考虑求出这棵支配树。
考虑运用 dfs 序和生成树完成该问题,为了方便,以下的任意节点 \(u\) 的编号为 \(dfn_u\)。
于是发明支配树的强者建立了一个新的概念:半支配点。如果 \(u\) 半支配 \(v\),那么 \(u\) 必须满足存在一条到 \(v\) 的路径使得,除了 \(u,v\) 两点以外路径中其它点 \(v_k\) 都要大于 \(v\),并且 \(u\) 是满足上述条件的编号(dfs 序)最小的点。这跟支配点有什么关系?带着问题推导到后面就知道了。
我们先设点 \(u\) 的支配点为 \(idom(u)\),半支配点为 \(sdom(u)\)。
结论 0:
显然能到达 \(u\) 的点集中,只有 \(u\) 的父亲小于 \(u\),其余均大于 \(u\)。
结论 1:
\(sdom(u)\) 必然小于 \(u\)。
证明:考虑 \(u\) 的父亲就是满足条件的点。
结论 2:
在生成树中,\(idom(u)\) 必然是 \(u\) 的祖先(或本身)。
证明:考虑到从根到 \(u\) 就存在一条路径。
结论 3:
在生成树中,\(sdom(u)\) 必然是 \(u\) 的祖先。
证明:\(sdom(u)\) 小于 \(u\),而在构建生成树的过程中,如果 \(v\) 小于 \(u\) 且存在 \(v\) 到 \(u\) 的路径,那么树中 \(v\) 一定是 \(u\) 的祖先。
结论 4:
在生成树中,\(idom(u)\) 必然是 \(sdom(u)\) 的祖先(或本身)。
证明:显然。
通过这些结论,我们可以得到第一个定理:
\[sdom(u)=\min(\{v|(v,u)\in E,v<u\}\cup\{sdom(w)|w>u\land\exists v>u,(u,v)\in E,\text{s.t.} w \text{是} v \text{的祖先或} w=v) \]证明:前一半是显然的,并且我们可以知道右边的式子显然要大于等于 \(sdom(u)\)。
然后,我们在半支配路径 \(sdom(u),v_1,v_2,\cdots,v_k,u\) 中找到 \(v_k\) 最小的祖先 (或 \(v_k\)),记为 \(v_j\),我们接下来证明 \(sdom(u)\) 是满足 \(v_j\) 半支配点条件的点,即证明 \(\forall 1\le i<j,v_i>v_j\)。若存在 \(v_i<v_j\),那么 \(v_i\) 显然不能作为 \(v_j\) 的祖先,而 \(v_i\) 能到达 \(v_j\),则说明在建立生成树时,只有 \(2\) 种情况,一种是 \(v_i\) 是 \(v_j\) 的祖先,\(v_i<v_j\),一种是 \(v_i\) 不为 \(v_j\) 祖先,且 \(v_i>v_j\)。而这两种情况与刚刚的条件不存在交集,故不存在 \(v_i<v_j\)。
所以该式子中包含了 \(sdom(u)\),我们完成了证明。
于是,我们便有了一种快速求解半支配点的方法。我们按照 dfs 序从后往前做,利用带权并查集维护刚刚的式子即可。
求出来半支配点,我们就可以求解支配树了!
首先有个非常丑陋的方法,也比较难写,非常不推荐。
就是我们在生成树基础上将 \(sdom(u)\) 向 \(u\) 连边,这样会形成一个 DAG,而在 DAG 上跑支配树是简单的。那么为什么这样是对的呢?显然,我们对这种做法的第一感觉是我们丢掉了一些关系,也就是说我们成为支配点的条件较原图变得似乎更宽了。于是我们考虑严谨证明 DAG 上的每一个支配关系在原图中照样存在。
首先在建立生成树时,如果存在从 \(v\) 到 \(u\) 的路径,那么只有 \(2\) 种情况,一种是 \(v\) 是 \(u\) 的祖先,\(v<u\),一种是 \(v\) 不为 \(u\) 祖先,且 \(v>u\)。
我们只考虑证明先经过一段树边,再经过一段非树边到 \(u\) 的情况(不经过 DAG 情况下的 \(idom(u)\))。其他情况没有任何必要考虑,如果产生了多次树边和非树边的切换,为什么前面冗余的切换不能全走树边?所以只有这种情况有必要考虑。注意到,经过的这一段非树边可以形成一段符合条件的半支配路径,而半支配边已经建好了,且其支配点肯定是其半支配点的祖先,故在原图中也不可能存在不经过 \(idom(u)\) 就能到达 \(u\) 的情况。
所以,我们可以在这样一个 DAG 中求出支配树。
而第二种方法才是主流方法。这里需要另外两个定理。
定理 1:对于任意节点 \(u\),设 \(v\) 是 \(sdom(u)\) 到 \(u\) 这条链上半支配点最小的点(不包括 \(u\) 和 \(sdom(u)\)),若 \(sdom(v)\ge sdom(u)\),则 \(idom(u)=sdom(u)\)。
(注意!链是指树上的链,我学这个内容时理解错了,卡了很久!)
证明:考虑 \(sdom(u)\) 子树外一点 \(v\),若 \(v\) 能到达 \(u\),则 \(v>u>sdom(u)\)。所以,首先 \(v\) 不能为 \(sdom(u)\) 的祖先。然后,我们可以发现如果 \(v\) 能到达 \(u\),会先到达 \(sdom(u)\) 与 \(u\) 之间的路径的一个点 \(w\),然而如果是这样,\(sdom(w)\) 肯定会小于 \(sdom(u)\),这并不满足条件。
定理 2:对于任意节点 \(u\),设 \(v\) 是 \(sdom(u)\) 到 \(u\) 这条链上半支配点最小的点,若 \(sdom(v)<sdom(u)\),则 \(idom(u)=idom(v)\)。
证明:首先,\(idom(u)\) 肯定是 \(idom(v)\) 的祖先(或 \(idom(v)\)),否则将存在一条路径 \(1\rightarrow idom(v)\rightarrow v\rightarrow u\)。故我们需要证明不存在从 \(1\) 出发不经过 \(idom(v)\) 的路径到 \(u\)。首先这条路径末端肯定会在 \(u\) 与 \(sdom(u)\) 之间(其实是在 \(u\) 和 \(v\) 之间,因为如果在 \(v\) 上面就说明有不经过 \(idom(v)\) 到达 \(v\) 的路径,这是不可能的),因为如果不在并直接到 \(u\),则 \(sdom(u)\) 将会被更新。然而如果在这条链之间,则相当与 \(sdom(u)\) 到 \(u\) 这条链之间存在一点的半支配点小于 \(idom(v)\),这绝对不可能。
于是,我们发现这样子就可以转移了。支配树的代码实现非常容易,我们整个按 dfs 序从后往前转移,\(idom\) 和 \(sdom\) 一起求。实现时,我们建立半支配树,每到一个点我们先帮以自己为半支配点的节点求出 \(idom\),然后再求自己的 \(sdom\),多么的无私啊,具体实现看代码:
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 100000000000000
#define pii pair <int, short>
using namespace std;
constexpr int N = 2e5 + 5, P = 998244353;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, m;
vector <int> g[N], fg[N], vec[N];
int dfn[N], id[N], tim;
int idom[N], sdom[N], fa[N];
struct DSU
{
int fa[N], mn[N];
void init ()
{
rep (i, 1, n) fa[i] = mn[i] = i;
}
int find (int x)
{
if (x == fa[x]) return x;
int fx = find (fa[x]);
if (dfn[sdom[mn[x]]] > dfn[sdom[mn[fa[x]]]]) mn[x] = mn[fa[x]];
return fa[x] = fx;
}
} d;
void dfs (int u)
{
id[dfn[u] = ++ tim] = u;
for (auto v : g[u]) if (! dfn[v]) dfs (v), fa[v] = u;
}
int ans[N];
int main ()
{
n = rd (), m = rd ();
rep (i, 1, m)
{
int u = rd (), v = rd ();
g[u].eb (v);
fg[v].eb (u);
}
dfs (1);
rep (i, 1, n) sdom[i] = i;
d.init ();
rrp (i, 1, n)
{
int u = id[i];
if (! u) continue;
for (auto v : vec[u])
{
d.find (v);
if (sdom[d.mn[v]] == u) idom[v] = u;
else idom[v] = d.mn[v]; //为什么可以这样?考虑到最后的点一定会指向自己的sdom,递归过来即可
}
if (i == 1) continue;
for (auto v : fg[u])
{
if (! dfn[v]) continue;
if (dfn[v] < dfn[sdom[u]]) sdom[u] = v;
else
{
d.find (v);
if (dfn[sdom[u]] > dfn[sdom[d.mn[v]]]) sdom[u] = sdom[d.mn[v]];
}
}
vec[sdom[u]].eb (u);//建立半支配树
d.fa[u] = fa[u];//更新父亲,以便求祖先的最小sdom
}
rep (i, 1, n) if (idom[id[i]] ^ sdom[id[i]]) idom[id[i]] = idom[idom[id[i]]];
rrp (i, 2, n)
{
++ ans[id[i]];
ans[idom[id[i]]] += ans[id[i]];
}
++ ans[1];
rep (i, 1, n) printf ("%d ", ans[i]);
}
于是,我们便学会了支配树。
标签:sdom,支配,int,笔记,学习,fa,dfn,idom From: https://www.cnblogs.com/lalaouyehome/p/18303484