DDOSvoid's Blog

圆方树

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

简介

原图中的点为原点，新建出来的点为方点

圆方树

据说最早的圆方树是用来操作仙人掌的，所以我们只能称一般图的圆方树为广义圆方树了

普通圆方树比较简单，我们只需要将边仙人掌中的每个简单环上的边都扔掉，对于每个简单环都建一个方点，然后将简单环上的点向方点连边

1275607-20190409214640146-1846324450.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int u) {
    static int cnt = 0;
    dfn[u] = low[u] = ++cnt;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (v == fa[u]) continue;
        if (!dfn[v]) {
            fa[v] = u; fr[v] = w;
            dfs(v); low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], dfn[v]);
        if (low[v] > dfn[u]) Add_Edge(u, v, w); // 圆 - 圆
    }
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (u == fa[v] || dfn[v] < dfn[u]) continue;
        solve(u, v, w); // 圆 - 方
    }
}

例题

Luogu P5236 【模板】静态仙人掌 求仙人掌上任意两点最短距离

广义圆方树

跟普通圆方树没有太大的区别，大概就是对于每个点双新建一个方点，然后将点双中的所有点向方点连边

需要注意的是我的写法中，两个点一条边也视为一个点双

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dfn[maxn], low[maxn], num; stack<int> S;
void tarjan(int u, int fa) {
    static int cnt = 0;
    dfn[u] = low[u] = ++cnt; S.push(u); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u); low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++num; int t;
                do {
                    t = S.top(); S.pop(); 
                    Add_Edge(t, num); 
                } while (t != v);
                Add_Edge(u, num);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

性质

  1. 树上的每一条边都连接了一个圆点和一个方点
  2. 每个点双有唯一的方点
  3. 一条从圆点到圆点的树上简单路径代表原图的中的一堆路径，其中圆点是必须经过的，而方点(指的是与方点相连的点双）是可以随便走的，也可以理解成原图中两点简单路径的并