圆方树
前置知识：
- 点双连通分量
- tarjan 求点双
对于一个无向图，在维护某些信息时可以利用圆方树的方法把原图转为一棵树来处理
我们称在原图上的点是 圆点
对于每个点双联通分量，新建一个连向点双内所有点的新点，称其为 方点
点双内的所有点除了向 方点 连边以外不向点双内其他点连边，换句话说一个点双内，以方点为中心形成了一个菊花图的形状
来自WC的PPT(和小粉兔的博客)
点双的数量 \(<n\)，所以圆方树的点数 \(<2n\)
显然如果原图有 \(k\) 个联通块，则原图会形成一个 \(k\) 棵树组成的森林
Tarjan 构造圆方树
利用 Tarjan 可以在求点双的同时顺便把圆方树建出来，在统计同一个点双里面的点的时候加一个向方点连边的过程即可
为了风格统一这里没有使用通常建圆方树时点入栈的方法，而是平时tarjan的边入栈
void dfs(int u, int fa) {
low[u] = rnk[u] = ++dfc;
int child = 0;
for(int i : G[u]) {
auto e = E[i];
int v = e.v;
if(!rnk[v]) {
stk.push(e);
dfs(v, u);
low[u] = min(low[v], low[u]);
child++;
if(low[v] >= rnk[u]) {
is_cut[u] = true;
bcccnt++;
while(1) {
auto x = stk.top();
stk.pop();
//建圆方树
if(bccnu[x.u] != bcccnt)
add2(x.u, n + bcccnt), bccnu[x.u] = bcccnt;
if(bccnu[x.v] != bcccnt)
add2(x.v, n + bcccnt), bccnu[x.v] = bcccnt;
if(x == e)
break;
}
}
} else if(rnk[v] < rnk[u] && v != fa) {
stk.push(e);
low[u] = min(low[u], rnk[v]);
}
}
if(fa == 0 && child == 1)
is_cut[u] = 0;
}
inline void tarjan() {
for(int u = 1; u <= n; u++)
if(!rnk[u])
dfs(u, 0);
}
圆方树的性质
- 圆方树中圆点和方点交替出现
Example 1: UVA1464
给你一个 \(n\) 个点 \(m\) 条边的无向图，问从边 \(S\) 出发到边 \(T\) 无论怎么走都必须经过的点有几个
Solution
把圆方树建出来，答案就是 $u$ 和 $v$ 在树上简单路径上的圆点数量。由于圆点和方点交替出现，分类讨论可以知道 $u$ 和 $v$ 之间圆点数量是 $(dep[u] + dep[v] - 2 * dep[lca]) / 2 - 1$
Code
``` #includeusing namespace std;
const int N = 1e4 + 10, M = 10 * N;
int n, m;
vector
int cnt;
struct edge {
int u, v;
edge() {}
edge(int _u, int _v) {
u = _u, v = _v;
}
bool operator == (const edge& x) const {
return x.u == u && x.v == v;
}
}E[M << 2], T[M << 2];
inline void add(int u, int v) {
E[cnt++] = edge(u, v);
E[cnt++] = edge(v, u);
G[u].push_back(cnt - 2);
G[v].push_back(cnt - 1);
}
int low[N], rnk[N], dfc;
int bccnu[N], is_cut[N], bcccnt;
int cnt2;
stack
void add2(int u, int v) {
//printf("Add Edge: %d %d\n", u, v);
T[cnt2++] = edge(u, v);
T[cnt2++] = edge(v, u);
tr[u].push_back(cnt2 - 2);
tr[v].push_back(cnt2 - 1);
}
void dfs(int u, int fa) {
low[u] = rnk[u] = ++dfc;
int child = 0;
for(int i : G[u]) {
auto e = E[i];
int v = e.v;
if(!rnk[v]) {
stk.push(e);
dfs(v, u);
low[u] = min(low[v], low[u]);
child++;
if(low[v] >= rnk[u]) {
is_cut[u] = true;
bcccnt++;
while(1) {
auto x = stk.top();
stk.pop();
if(bccnu[x.u] != bcccnt)
add2(x.u, n + bcccnt), bccnu[x.u] = bcccnt;
if(bccnu[x.v] != bcccnt)
add2(x.v, n + bcccnt), bccnu[x.v] = bcccnt;
if(x == e)
break;
}
}
} else if(rnk[v] < rnk[u] && v != fa) {
stk.push(e);
low[u] = min(low[u], rnk[v]);
}
}
if(fa == 0 && child == 1)
is_cut[u] = 0;
}
inline void tarjan() {
for(int u = 1; u <= n; u++)
if(!rnk[u])
dfs(u, 0);
}
int fa[21][N << 1];
int dep[N << 1];
void tree(int u, int f) {
fa[0][u] = f;
dep[u] = dep[f] + 1;
for(int i : tr[u]) {
auto x = T[i];
int v = x.v;
if(v == f)
continue;
tree(v, u);
}
}
int LCA(int u, int v) {
if(dep[u] < dep[v])
swap(u, v);
for(int i = 20; i >= 0; i--)
if(dep[fa[i][u]] >= dep[v])
u = fa[i][u];
if(u == v)
return u;
for(int i = 20; i >= 0; i--) {
if(fa[i][u] != fa[i][v]){
u = fa[i][u], v = fa[i][v];
}
}
u = fa[0][u];
return u;
}
inline void clear() {
for(int u = 1; u <= n; u++)
G[u].clear();
for(int u = 1; u <= n + bcccnt; u++)
tr[u].clear();
memset(is_cut, 0, (n + 1) * sizeof(int));
memset(bccnu, 0, (n + 1) * sizeof(int));
memset(low, 0, (n + 1) * sizeof(int));
memset(rnk, 0, (n + 1) * sizeof(int));
memset(fa, 0, sizeof(fa));
memset(dep, 0, sizeof(dep));
cnt = cnt2 = dfc = bcccnt = 0;
}
int calc(int u, int v) {
int lca = LCA(u, v);
return (dep[u] + dep[v] - 2 * dep[lca]) / 2 - 1;
}
int query(int u, int v) {
int a[2], b[2];
a[0] = E[(u - 1) * 2].u, a[1] = E[(u - 1) * 2].v;
b[0] = E[(v - 1) * 2].u, b[1] = E[(v - 1) * 2].v;
int ans = 0;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
ans = max(ans, calc(a[i], b[j]));
return ans;
}
int main() {
// freopen("input.txt", "r", stdin);
while(scanf("%d%d", &n, &m) == 2 && (n | m)) {
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
tarjan();
for(int u = 1; u <= n + bcccnt; u++)
if(!dep[u])
tree(u, 0);
for(int k = 1; k < 21; k++)
for(int u = 1; u <= n + bcccnt; u++)
fa[k][u] = fa[k-1][fa[k-1][u]];
int Q;
scanf("%d", &Q);
for(int i = 1; i <= Q; i++) {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", query(u, v));
}
clear();
}
return 0;
}
</details>
## 例题
## 仙人掌上圆方树