圆方树学习笔记

圆方树可以解决仙人掌或一类无向图问题。

建树

通过 tarjan 缩点双为方点,原来的点为圆点。每个圆点连边到自己所属的点双方点,跨点双的圆点连边转换为圆方点之间的连边。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct edge {
int tot, flag, hed[N], nxt[M], to[M];
edge () { tot = 2; }
void link(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}
} G1, G2;

void tarjan(int u, int father) {
++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
if (v != father) {
if (!dfn[v]) {
tarjan(v, u), low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
G2.link(u, ++tot), ++val[tot]; int x;
do {
x = stk[top--], ins[x] = 0;
G2.link(x, tot), ++val[tot];
} while (x != v);
}
} else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
}
}
  • 需要注意的是,根节点所在的点双的方点并不会创建,在大多数情况下,这并不会有影响,可根据题目的需要取舍。

性质

由此我们可以发现一些有趣的性质:

  • 现在总点数与原来的点数同阶,现在的总边数与原来的总边数同阶
  • 所有边都是圆点和方点之间的连边,即不存在圆圆边或方方边

例题

[APIO2018] 铁人两项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// =================================
// author: memset0
// date: 2018.12.12 23:54:19
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define int long long
namespace ringo {
typedef long long ll;

template < class T > inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template < class T > inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template < class T > inline void maxd(T &a, T b) { if (b > a) a = b; }
template < class T > inline void mind(T &a, T b) { if (b < a) a = b; }
template < class T > inline void print(T x, char c) { print(x), putchar(c); }

const int N = 2e5 + 10, M = 8e5 + 10;
int n, m, top, tot, ans, tim, base;
int dfn[N], low[N], ins[N], stk[N], son[N], siz[N], val[N];

struct edge {
int tot, flag, hed[N], nxt[M], to[M];
edge () { tot = 2; }
void link(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}
} G1, G2;

void tarjan(int u, int father) {
++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
for (int i = G1.hed[u]; i; i = G1.nxt[i]) {
int v = G1.to[i];
if (v != father) {
if (!dfn[v]) {
tarjan(v, u), low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
G2.link(u, ++tot), ++val[tot]; int x;
do {
x = stk[top--], ins[x] = 0;
G2.link(x, tot), ++val[tot];
} while (x != v);
}
} else if (ins[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
}
}

void dfs(int u, int father) {
if (u <= n) val[u] = -1, siz[u] = 1;
int sum = 0;
for (int i = G2.hed[u], v = G2.to[i]; i; i = G2.nxt[i], v = G2.to[i])
if (v != father) {
dfs(v, u);
siz[u] += siz[v];
sum += (ll)siz[v] * (base - siz[v]);
}
sum += (ll)(siz[u]) * (base - siz[u]);
if (u <= n) sum += base - 1;
ans += (ll)val[u] * sum;
}

void main() {
read(n), read(m);
for (int i = 1, u, v; i <= m; i++) {
read(u), read(v);
G1.link(u, v);
}
tot = n;
G2.flag = true;
for (int i = 1; i <= n; i++)
if (!dfn[i]) {
base = 0;
tarjan(i, 0);
dfs(i, 0);
}
print(ans, '\n');
}

} signed main() { return ringo::main(), 0; }

[洛谷4320] 道路相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// =================================
// author: memset0
// date: 2018.12.13 23:55:39
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
namespace ringo {
typedef long long ll;

template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void maxd(T &a, T b) { if (b > a) a = b; }
template <class T> inline void mind(T &a, T b) { if (b < a) a = b; }
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e6 + 10;
int n, m, u, v, w, t, tot, pos, tim, hed;
typedef int R1[N]; R1 siz, son, fa, dep, top, low, dfn, ins, stk, id, wid;

struct graph {
int tot, hed[N], nxt[N << 1], to[N << 1];
graph () { tot = 2; }
inline void add_edge(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}
} G1, G2;

void tarjan(int u, int father) {
dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++hed] = u;
for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
if (v != father) {
if (!dfn[v]) {
tarjan(v, u), low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
G2.add_edge(u, ++tot);
int x; do {
x = stk[hed--];
ins[x] = false, G2.add_edge(x, tot);
} while (x != v);
}
} else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
}
}

inline int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) std::swap(u, v);
v = fa[top[v]];
}
return dep[u] < dep[v] ? u : v;
}

void dfs(int u) {
siz[u] = 1;
for (int i = G2.hed[u], v = G2.to[i]; i; i = G2.nxt[i], v = G2.to[i])
if (v != fa[u]) {
fa[v] = u, dep[v] = dep[u] + 1, dfs(v), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}

void dfs(int u, int toppoint) {
top[u] = toppoint, id[u] = ++pos, wid[id[u]] = u;
if (siz[u] == 1) return;
dfs(son[u], toppoint);
for (int i = G2.hed[u], v = G2.to[i]; i; i = G2.nxt[i], v = G2.to[i])
if (v != fa[u] && v != son[u])
dfs(v, v);
}

void main() {
read(n), read(m);
for (int i = 1; i <= m; i++) {
read(u), read(v);
G1.add_edge(u, v);
}
tot = n;
for (int i = 1; i <= n; i++)
if (!dfn[i]) {
tarjan(i, 0), dep[i] = 1;
dfs(i), dfs(i, i);
}
read(m);
for (int i = 1; i <= m; i++) {
read(u), read(v), t = lca(u, v);
w = dep[u] + dep[v] - (dep[t] << 1) + 1;
print((w + 1) >> 1, '\n');
}
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×