支配树

约 43 个字 101 行代码 预计阅读时间 1 分钟

指定起点/根，如果到达v必须经过u，那么u支配了v

每个点向其最近支配点连边，形成了支配树

vector<int> G[N]; // 根据原图建的支配树图
namespace DominatorTree
{
    struct edge
    {
        int v, nxt;
    } e[N * 4];
    int tot, dfc, dfn[N], pos[N], sdm[N], idm[N], f[N], mn[N], fth[N], h[3][N * 2];
    void init(int n)
    {
        tot = dfc = 0;
        memset(dfn, 0, sizeof(int) * (n + 1));
        memset(idm, 0, sizeof(int) * (n + 1));
        memset(f, -1, sizeof(int) * (n + 1));
        for (int i = 0; i < 3; ++i)
            memset(h[i], 0, sizeof(int) * (n * 2 + 1));
        for (int i = 1; i <= n; ++i)
            mn[i] = i;
        for (int i = 1; i <= n; ++i)
            sdm[i] = i;
        for (int i = 1; i <= n; ++i)
            G[i].clear();
    }
    void add(int x, int u, int v)
    {
        e[++tot] = {v, h[x][u]};
        h[x][u] = tot;
    }
    void link(int u, int v)
    {
        add(0, u, v);
        add(1, v, u);
    }
    void dfs(int u)
    {
        dfn[u] = ++dfc;
        pos[dfc] = u;
        for (int i = h[0][u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (dfn[v])
                continue;
            fth[v] = u;
            dfs(v);
        }
    }
    int find(int x)
    {
        if (f[x] == -1)
            return x;
        int tmp = f[x];
        f[x] = find(f[x]);
        if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]])
            mn[x] = mn[tmp];
        return f[x];
    }
    void tarjan(int st)
    {
        dfs(st);
        for (int i = dfc; i >= 2; --i)
        {
            int u = pos[i], res = INF;
            for (int j = h[1][u]; j; j = e[j].nxt)
            {
                int v = e[j].v;
                if (!dfn[v])
                    continue;
                find(v);
                if (dfn[v] < dfn[u])
                    res = std::min(res, dfn[v]);
                else
                    res = std::min(res, dfn[sdm[mn[v]]]);
            }
            sdm[u] = pos[res];
            f[u] = fth[u];
            add(2, sdm[u], u);
            u = fth[u];
            for (int j = h[2][u]; j; j = e[j].nxt)
            {
                int v = e[j].v;
                find(v);
                if (u == sdm[mn[v]])
                    idm[v] = u;
                else
                    idm[v] = mn[v];
            }
            h[2][u] = 0;
        }
        for (int i = 2; i <= dfc; ++i)
        {
            int u = pos[i];
            if (idm[u] != sdm[u])
                idm[u] = idm[idm[u]];
        }
        for (int i = dfc; i >= 2; --i)
            G[idm[pos[i]]].push_back(pos[i]);
    }
};
DominatorTree::init(n);
DominatorTree::link(u, v);
DominatorTree::tarjan(1);