支配树

· · 个人记录

支配树能够解决有向图必经点的问题。

定义，定理与约定

DAG 的支配树的构造

外向树的支配树显然是其本身。

我们可以从 DAG 的源点开始，按照拓扑序遍历。当访问到一个点的时候，其最近支配点一定是其所有入边端点的支配树的 LCA（想走到 u，必须先走其入边端点）。

据此可以构建 DAG 的支配树。

相关题目：P2597 [ZJOI2012]灾难 ； CF757F Team Rocket Rises Again

关键代码：

inline void tuopu() {
    que[++rear] = s;
    while (front < rear) {
        int cur = que[++front];
        int lca = 0;//Attention!!
        for (register unsigned int i = 0; i < iV[cur].size(); ++i) {
            int to = iV[cur][i];
            if (!lca)   lca = to;
            else    lca = get_lca(lca, to);//Attention!! : to
        }
        f[cur][0] = lca;
        for (register int i = 1; i <= 20; ++i)
            f[cur][i] = f[f[cur][i - 1]][i - 1];
        for (register unsigned int i = 0; i < V[cur].size(); ++i) {
            int to = V[cur][i];
            --d[to];
            if (!d[to]) que[++rear] = to;
        }
        dep[cur] = dep[f[cur][0]] + 1;
    }
}

普通有向图的支配树的构造

另一些定义及定理

证明：至少 u 的 dfs 树上父亲 fa 可以当作 sdom[u]，因此子树不可能；如果 sdom[u] 在其它树上，那么至少能在树上找到一条路径 anc -> sdom[u] -> u，其中 anc（u 的祖先）会作为 sdom[u]。

证明：不会

感性证明：我们站在 dfs 树为主体的角度看。显然 sdom[cur] 下面不会出现支配点，因为至少存在树上路径和 sdom[cur] -> cur 路径能够到达 cur。所以 sdom[cur] 下面的点到 cur 的非树边都可以删除。至于 sdom[cur] 的上面如果还有向 cur 的连边的话，那么为什么 sdom[cur] 不是那个祖先呢？

构造方法

需要构造出所有点的半支配点，然后删除原图边，半支配点向该点连边，转化为 DAG 上的问题。

如何构造半支配点？我们按编号从大到小枚举，对于每个点寻找反向边。首先如果对于当前节点 v，存在一个 u -> v，且 u < v，那么可以直接用 u 来更新 sdom[v]；如果 u -> v，并且 u > v，那么 u 在之前一定已经遍历过了，那么根据定义我们沿着 u 到源点的链中已经遍历过的部分向上走，用路径上的 sdom 依次更新 sdom[v]。这个过程可以用边带权并查集优化。

关键代码：

int sdom[N];
int fa[N], mn[N];
int find(int cur) {
    if (fa[cur] == cur) return cur;//Attention!!!!!!!!!!!
    int faa = fa[cur];
    int anc = find(fa[cur]);
    MIN(mn[cur], mn[faa]);//Attnetion!!!!!
    fa[cur] = anc;
    return anc;
}
inline void get_sdom() {
    for (register int i = 1; i <= n; ++i)   fa[i] = mn[i] = sdom[i] = i;
    for (register int i = n; i > 1; --i) {
        int res = n;
        for (register unsigned int j = 0; j < iV[i].size(); ++j) {
            int to = iV[i][j];
            if (to < i) MIN(res, to);
            else    find(to), MIN(res, mn[to]);//Attention!!!!
        }
        sdom[i] = res; fa[i] = dfa[i];
        MIN(mn[i], res);
    }
    sdom[1] = 0;
}

然后再建出 DAG 跑支配树即可。

模板

//P5180
int dfn[N], dcnt, mp[N], s;
int dfa[N];
void dfs_init(int cur) {
    dfn[cur] = ++dcnt;
    mp[dcnt] = cur;
    for (register int i = head[cur]; i; i = e[i].nxt) {
        int to = e[i].to;
        if (!dfn[to])   dfs_init(to), dfa[dfn[to]] = dfn[cur];
    }
}

int sdom[N];
int fa[N], mn[N];
int find(int cur) {
    if (fa[cur] == cur) return cur;//Attention!!!!!!!!!!!
    int faa = fa[cur];
    int anc = find(fa[cur]);
    MIN(mn[cur], mn[faa]);//Attnetion!!!!!
    fa[cur] = anc;
    return anc;
}
inline void get_sdom() {
    for (register int i = 1; i <= n; ++i)   fa[i] = mn[i] = sdom[i] = i;
    for (register int i = n; i > 1; --i) {
        int res = n;
        for (register unsigned int j = 0; j < iV[i].size(); ++j) {
            int to = iV[i][j];
            if (!dfn[to])   continue;
            if (to < i) MIN(res, to);
            else    find(to), MIN(res, mn[to]);//Attention!!!!
        }
        sdom[i] = res; fa[i] = dfa[i];
        MIN(mn[i], res);
    }
    sdom[1] = 0;
}

int d[N];
int que[N], front, rear;
int f[N][21], dep[N];
inline int get_lca(int u, int v) {
    if (dep[u] < dep[v])    swap(u, v);
    for (register int i = 20; ~i; --i)
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    if (u == v) return u;
    for (register int i = 20; ~i; --i)
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
inline void tuopu() {
    que[++rear] = s;
    dep[0] = -1;
    while (front < rear) {
        int cur = que[++front], lca = 0;
        for (register unsigned int i = 0; i < iV[cur].size(); ++i) {
            int to = iV[cur][i];
            if (!lca)   lca = to;
            else    lca = get_lca(lca, to);
        }
        f[cur][0] = lca; dep[cur] = dep[lca] + 1;//Attention!!!!!
        for (register int i = 1; i <= 20; ++i)
            f[cur][i] = f[f[cur][i - 1]][i - 1];
        for (register int i = head[cur]; i; i = e[i].nxt) {
            int to = e[i].to;
            --d[to];
            if (!d[to]) que[++rear] = to;
        }
    }
}

int siz[N];
void dfs_siz(int cur) {
    siz[cur] = 1;
    for (register int i= head[cur]; i; i = e[i].nxt) {
        int to = e[i].to;
        dfs_siz(to);
        siz[cur] += siz[to];
    }
}

inline void work() {
    memset(head, 0, sizeof(head));
    ecnt = 0;
    for (register int i = 2; i <= n; ++i)   addedge(f[i][0], i);
    dfs_siz(s);
}

int ans[N];
int main() {
    read(n), read(m);
    for (register int i = 1; i <= m; ++i) {
        int u, v; read(u), read(v);
        addedge(u, v);
    }
    dfs_init(1); s = dfn[1];

    for (register int i = 1; i <= n; ++i) {
        for (register int j = head[i]; j; j = e[j].nxt) {
            int to = e[j].to;
            aded(dfn[to], dfn[i]);
        }
    }
    memset(head, 0, sizeof(head));
    ecnt = 0;
    for (register int i = 1; i <= n; ++i) {
        for (register unsigned int j = 0; j < iV[i].size(); ++j) {
            int to = iV[i][j];
            addedge(to, i);
        }
    }

    get_sdom();

    memset(head, 0, sizeof(head));
    ecnt = 0;
    for (register int i = 1; i <= n; ++i)
        iV[i].clear();
    for (register int i = 2; i <= n; ++i)
        addedge(sdom[i], i), ++d[i], aded(i, sdom[i]),
        addedge(dfa[i], i), ++d[i], aded(i, dfa[i]);//Attention!!!!!!
    tuopu();
    work();
    for (register int i = 1; i <= n; ++i)
     ans[mp[i]] = siz[i];
    for (register int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);//Attention!!!!!!!!!!!!!!
    puts("");
    return 0;
}

记忆方法

菜菜的我只好死记硬背

DAG 很好理解，就直接把所有前驱（入边）的 LCA 求一求即可。

有向图需要背过的是：