圆方树学习笔记

Archippus

7个月前更新

130

元方树。

下文除特殊强调外，所有图皆为无向图。

引入

割点：在图中，删除某个点后，导致图不再连通的点。
点双连通：在一张图中，取两个点 \(u\)、\(v\)，无论删去哪个点（除 \(u\)、\(v\) 自身外），\(u\)、\(v\) 都能连通，我们就说 \(u\) 和 \(v\) 点双连通。
点双连通分量（后文称点双）：对于一个无向图中的极大点双连通的子图，我们称这个子图为一个点双连通分量。

（from OI Wiki）

（下文中 \(u \leftrightarrow v\) 表示 \(u\) 和 \(v\) 在同一个点双里，这只是我个人的写法，实在懒得写了）

但点双性质实在不优秀，\(a \leftrightarrow b, b \leftrightarrow c\) 并不能推出 \(a \leftrightarrow c\)。

定义两条边相邻为：

两条边有公共顶点。

定义两条边属于同一个点双：

设两条边为 \((a, b)\)、\((c, d)\)，满足 \(\forall (x, y) \in \{a, b\} \times \{c, d\}, x \leftrightarrow y\) 就称 \((a, b)\) 和 \((c, d)\) 属于同一个点双（即 \((a, b) \leftrightarrow (c, d)\)）。

发现把边的定义整出来似乎就优秀了。

结论 \(1\)：若 \((a, b) \leftrightarrow (c, d)\) 且 \((c, d) \leftrightarrow (e, f)\)，则 \((a, b) \leftrightarrow (e, f)\)

证明：

根据定义，\((a, b) \leftrightarrow (e, f)\) 等价与 \(\forall (x, y) \in \{a, b\} \times \{e, f\}, x \leftrightarrow y\)，

又 \((a, b) \leftrightarrow (c, d)\)、\((e, f) \leftrightarrow (c, d)\)。

则任意的二元组 \((x, y)\)（这是二元组，不是边），一定满足 \(x\)、\(y\) 都与 \(c\)、\(d\) 两点属于同一个点双。

我们从图中删掉 \(c\)、\(d\) 中的任意一个都可以通过另外一个点从 \(x\) 到达 \(y\)。

如果删除的点不是 \(c\)、\(d\) 也能到达（\(x \leftrightarrow c\)、\(y \leftrightarrow c\)、\(x \leftrightarrow d\)、\(y \leftrightarrow d\)，不连通才怪……）。

\(a \leftrightarrow e\)、\(a \leftrightarrow f\)、\(b \leftrightarrow e\)、\(b \leftrightarrow f\)。

得证。

（借用一下 OI Wiki 的图，侵删）

众所周知，一条返祖边（非树边）可以使原图多一个点双。

那什么时候才能使两个点双合并成一个点双呢？

考虑把所有边都对应一个点，如果产生了一个点双则将所有在原图中相邻的的边对应的点连起来（即上图蓝边）。

只要蓝边相邻就可合并为同一个点双。

结论 \(2\)：对于树上的一个点双，深度最浅的点只有一个儿子。

证明：
使用反证法。

若一个点双深度最浅的点有超过一个儿子。

则其儿子中任意两个点均可以通过删掉父亲使其不连通，与定义不符。

则一个点双深度最浅的点不会有超过一个儿子。

得证。

正题

概念

圆方树是什么？

把一张图的所有点双统计出来，并对于每一个点双，新建一个方点（原图的点为圆点）。

将点双内所有圆点之间的边断开（点双外不断），并连到新建的方点上，如下图。

（好吧还是 OI Wiki 的）

实现

跑点双最好用的还是 tarjan 啊……

记 \(\text{dfn}_i\) 为点 \(i\) 的 dfs 序。

\(\text{low}_i\) 为点 \(i\) 能够通过非树边到达的 dfs 序最小的点的 dfs 序（包括它本身）。

结论 \(3\)：根据 结论 \(2\)，对于任意一条树边 \((u, v)\)，满足 \(u \leftrightarrow v\) 且 \(u\) 为点双最浅的点。

均满足 \(\text{low}_v = \text{dfn}_u\)（或 \(\text{low}_v \ge \text{dfn}_u\)）。

证明：

既然 \(u\)、\(v\) 属于同一个点双，则其必有一条非树边连向上面。

则 \(v\) 点必能通过非树边走到 \(u\)。

它无法继续通过树边走到下面（结论 \(2\)）。

也无法通过另外一条非树边走到上面（若有非树边能通向上面，则 \(u\) 就不是点双最浅点了）。

后面基本就跟普通 tarjan 一样了，贴个代码（点双模板）：

void tarjan(int u) {
    st.push(u);               // 把节点放到栈里
    dfn[u] = low[u] = ++tot;  // 更新两个值
    for (int v : g[u]) {
        if (!dfn[v]) {                     // 没访问过
            tarjan(v);                     // 访问
            low[u] = min(low[u], low[v]);  // 更新
            if (low[v] >= dfn[u]) {        // 改成 == 也行
                d_tot++;                   // 点双个数加 1
                d[d_tot].push_back(u);     // 更新点双
                while (st.top() != v) {    // 用栈死命弹
                    int t = st.top();
                    d[d_tot].push_back(t);
                    st.pop();
                }
                d[d_tot].push_back(v);
                st.pop();
            }
        } else
            low[u] = min(low[u], dfn[v]);  // 更新
    }
    if (g[u].size() == 0) {  // 特判单独一个点
        d_tot++;
        d[d_tot].push_back(u);
    }
}

建一颗圆方树也就简单了（前文有注释的就没写了）：

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            chmin(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                h_tot++;                // 建立方点
                h[h_tot].push_back(u);  // 无向图
                h[u].push_back(h_tot);
                while (st.top() != v) {
                    int t = st.top();
                    h[h_tot].push_back(t);
                    h[t].push_back(h_tot);
                    st.pop();
                }
                h[h_tot].push_back(v);
                h[v].push_back(h_tot);
                st.pop();
            }
        } else {
            chmin(low[u], dfn[v]);
        }
    }
}

一个技巧：区分圆点方点的最好方法就是把方点的下标从 \(n + 1\) 开始，即 h_tot 的初值赋为 \(n\)。

胜利！！！

例题

洛谷 P4320 道路相遇

建一棵圆方树。

观察到 \(u\) 到 \(v\) 的路径的必经点就是圆方树上 \(u\) 到 \(v\) 的路径上的圆点个数。

题目就转换成了一个树上路径问题。

倍增 LCA 即可。

namespace zqh {
const int N = 1000005;

int n, m, q, dfn[N], low[N], tot, h_tot, f[N][25], dep[N];
stack<int> st;
vector<int> g[N], h[N];

void tarjan(int u) {  // 圆方树，注释前文有写
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            chmin(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                h_tot++;
                h[h_tot].push_back(u);
                h[u].push_back(h_tot);
                while (st.top() != v) {
                    int t = st.top();
                    h[h_tot].push_back(t);
                    h[t].push_back(h_tot);
                    st.pop();
                }
                h[h_tot].push_back(v);
                h[v].push_back(h_tot);
                st.pop();
            }
        } else {
            chmin(low[u], dfn[v]);
        }
    }
}

void dfs(int u, int fa, int dp) {  // LCA，不用说啦吧
    f[u][0] = fa;
    dep[u] = dp;
    for (int x : h[u]) {
        if (x == fa)
            continue;
        dfs(x, u, dp + 1);
    }
}

void build() {
    int t = log2(n);
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    int dep_max = 0;
    while ((1 << (dep_max)) <= dep[x]) {
        dep_max++;
    }
    for (int i = dep_max; i >= 0; i--) {
        if (dep[x] - (1 << i) >= dep[y]) {
            x = f[x][i];
        }
    }
    if (x == y)
        return x;
    for (int i = dep_max; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

void init() {
    cin >> n >> m;
    h_tot = n;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    dfs(1, 0, 1);
    build();
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << dis(u, v) / 2 + 1 << endl;  // 圆点个数
    }
}

void main() {
    init();
    solve();
}
}  // namespace zqh

应该还会加的……

来源链接：https://www.cnblogs.com/zphh/p/18496256

评分

欢迎为Ta评分