526互联

Template <支配树>

发布时间 2023-08-03 17:00:39作者: O2iginal

P5180 【模板】支配树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <iostream>
#include <vector>
using namespace std;

namespace dtree
{
    const int MAXN = 500020;
    // g原图； rg反图； dg 原图dfs树边 + sdm[u]->u边 构成的图
    vector<int> g[MAXN], rg[MAXN], dg[MAXN];
    // dfc：dfs计数； dfn：结点i的dfs访问序号； pos：第i个dfs访问的结点为pos[i]
    int dfn[MAXN], pos[MAXN], dfc;
    // pa：并查集；  val：并查集维护的距离，即i-sdm[i]路径上结点v中，满足条件的、dfn[sdm[v]]最小的 v
    // sdm：结点i的半支配节点  fa：结点i在原图dfs中的父节点  dom：结点i的直接支配结点
    // 注意：以下5个数组中的元素均不是原题中的结点序号，而是dfs后的dfn值（需要用pos数组转换回原序号）
    int pa[MAXN], fa[MAXN], val[MAXN], sdm[MAXN], dom[MAXN];

    void clear(int n)
    {
        dfc = 0;
        for (int i = 0; i <= n; i++)
        {
            pa[i] = val[i] = sdm[i] = fa[i] = dom[i] = dfn[i] = pos[i] = 0;
            g[i].clear();
            rg[i].clear();
            dg[i].clear();
        }
    }

    void add_edge(int x, int y) { g[x].push_back(y); }

    void merge(int x, int y) { pa[x] = y; }

    // 注意：这里并查集的元素用dfn表示，并不是图中结点名称（序号）
    // c 默认为0，此时返回当前维护的 x-sdm[x]路径上 的结点v中，dfs序 sdm[v] 最小的v （这里的v也是dfs序）
    //   当为1时，则返回正常的find(x)，即x元素的根节点
    int find(int x, int c = 0)
    {
        if (pa[x] == x) return c ? -1 : x;
        int p = find(pa[x], 1);
        if (p == -1) return c ? pa[x] : val[x];
        if (sdm[val[x]] > sdm[val[pa[x]]]) val[x] = val[pa[x]];  // 更新维护的最小sdm元素
        pa[x] = p;
        return c ? p : val[x];
    }

    void dfs(int u)
    {
        pos[dfn[u] = ++dfc] = u;
        pa[dfc] = sdm[dfc] = val[dfc] = dfc;
        for (int v : g[u])
        {
            if (dfn[v] == 0)
            {
                dfs(v);
                fa[dfn[v]] = dfn[u];
            }
            rg[dfn[v]].push_back(dfn[u]);
        }
    }

    // 通过idom返回支配树，idm[u]为结点u的直接支配点（支配树中u结点的父节点）
    // s 为支配树根节点
    int solve(int s, int *idom)
    {
        dfs(s);
        for (int u = dfc; u; u--)
        {
            for (int v : rg[u]) sdm[u] = min(sdm[u], sdm[find(v)]);
            if (u > 1) dg[sdm[u]].push_back(u);
            for (int v : dg[u])
            {
                int p = find(v);
                if (sdm[p] == u) dom[v] = u;
                else dom[v] = p;
            }
            if (u > 1) merge(u, fa[u]);
        }

        for (int i = 2; i <= dfc; i++) if (sdm[i] != dom[i]) dom[i] = dom[dom[i]];
        for (int i = 2; i <= dfc; i++) idom[pos[i]] = pos[dom[i]];
        return dfc;
    }
}


const int MAXN = 5e5 + 10;
int idom[MAXN];
vector<int> g[MAXN];
int siz[MAXN];

void dfs(int u)
{
    siz[u] = 1;
    for (auto v: g[u])
    {
        dfs(v);
        siz[u] += siz[v];
    }
}

void solv()
{
    int n, m; cin >> n >> m;
    dtree::clear(n);
    for (int i = 1; i <= m; i ++)
    {
        int u, v; cin >> u >> v;
        dtree::add_edge(u, v);
    }
    dtree::solve(1, idom);
    for (int i = 1; i <= n; i ++) g[idom[i]].push_back(i);
    dfs(1);
    for (int i = 1; i <= n; i ++) cout << siz[i] << ' ';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}