树与图的 dfs

树的 dfs

1
2
3
4
5
6
7
8
9
10
11
void dfs(int x) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (vis[y]) continue;
dfs(y);
}
}
int main() {
dfs(1);
}

树的 dfs 序

dfs-01

1
2
3
4
5
6
7
8
9
10
11
vector<int> a;
void dfs(int x) {
a.push_back(x);
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (vis[y]) continue;
dfs(y);
}
a.push_back(x);
}

树的深度

for e(x,y)\textbf{for} \ \forall e(x, y)
d(y)=d(x)+1\quad \quad d(y) = d(x) + 1

1
2
3
4
5
6
7
8
9
10
memset(d, 0, sizeof d);
void dfs(int x) {
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (vis[y]) continue;
d[y] = d[x] + 1;
dfs(y);
}
}

树的重心

树的重心非常重要,是点分治中的重要算法
dfs-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int res = inf, pos;
void gravity(int x, int &res) {
vis[x] = 1; size[x] = 1;
int maxpart = 0;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (vis[y]) continue;
dfs(y, res);
size[x] += size[y];
maxpart = max(maxpart, size[y]);
}
maxpart = max(maxpart, n - size[x]);
if (maxpart < res) {
res = maxpart;
pos = x;
}
}

图的连通块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int cnt = 0;
void dfs(int x) {
v[x] = cnt;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (v[y]) continue;
dfs(y);
}
}

int main() {
for (int i = 1; i <= n; i++) {
if (!v[i]) {
cnt++;
dfs(i);
}
}
}

树和图的 bfs

bfs的性质

  • bfs 是逐层扩展的,并且每一次出队列的时候,才把队头元素的子节点,放入队列中
    所以任何时刻,队列中的元素至多有22 个层次的节点
    其中一部分节点属于第ii 层,另一部分属于第i+1i+1
  • 在访问完第ii 层节点后,才会访问第i+1i+1
  • bfs 可以求出dd 数组,d(x)d(x) 表示从起点11 走到xx
    最少需要经过多少点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bfs() {
memset(d, 0, sizeof d);
queue<int> q;
q.push(1); d[1] = 1;
while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (d[y]) continue;
d[y] = d[x] + 1;
q.push(y);
}
}
}

拓扑排序

  • 拓扑排序适用于有向无环图 (dag)
  • 预处理入度数组deg[]\textbf{deg}[\cdots],把所有deg=0\textbf{deg}=0 的点入队
  • xfront()x \leftarrow \text{front}(),检查每一条边for (x,yk)\textbf{for} \ \forall (x, y_k)
    if deg[yk]=0\textbf{if} \ --\textbf{deg}[y_k] = 0push(yk)\textbf{push}(y_k)

Acwing164
用状态压缩来表示集合,不妨设f(x)f(x) 表示从xx 出发能够到达的点构成的集合

f(x)={x}((x,y)存在有向边f(y))f(x) = \{x\} \cup \left( \bigcup_{(x, y) \text{存在有向边}} f(y)\right)

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
const int maxn = 30000 + 10;
int head[maxn], ne[maxn], ver[maxn], deg[maxn], n, m, tot = 0;
vector<int> a;

void add(int x, int y) {
ver[++tot] = y; ne[tot] = head[x]; head[x] = tot;
deg[y]++;
}

void toposort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (deg[i] == 0) q.push(i);
}

while (q.size()) {
int x = q.front(); q.pop();
a.push_back(x);
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (--deg[y] == 0) q.push(y);
}
}
}

bitset<maxn> f[maxn];
void solve() {
for (int j = a.size()-1; j >= 0; j--) {
int x = a[j];
f[x][x] = 1;
for (int i = head[x]; i; i = ne[i]) {
f[x] |= f[ver[i]];
}
}

for (int i = 1; i <= n; i++) printf("%d\n", (int)f[i].count());
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

// get edge
memset(head, 0, sizeof head);
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
}

toposort();
solve();
}

树的直径

两次 bfs 求树的直径

  • 11 出发执行bfs(1)\textbf{bfs}(1),求出与出发点最远,即d[  ]\text{d}[\ \ ] 最大的节点
    记为aaaa 就是直径的一端
  • aa 出发执行bfs(a)\textbf{bfs}(a),求出最远的点bb,则(a,b)(a, b) 为树的一条直径
    • 在这个过程中,当每个点第一次被访问的时候,假如当前队列中取出xx
      对于边(x,y), vis[y]=0(x, y), \ vis[y] = 0,可以实时维护前驱信息
      pre(y)=x\textbf{pre}(y) = x
      最后从bb 回到aa,可以得到具体的直径方案

codeforces1294F
codeforces1294f

  • bfs(1)\textbf{bfs}(1) 并记录dd 最远点,aposa \leftarrow pos
  • bfs(a)\textbf{bfs}(a) 并记录dd 信息
    da[ ]d[ ],bposda[\ ] \leftarrow d[\ ], \quad b \leftarrow pos
  • bfs(b)\textbf{bfs}(b) 并记录dd 信息,db[ ]d[ ]db[\ ] \leftarrow d[\ ]
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
const int maxn = 400000 + 10;
int head[maxn], ne[maxn], ver[maxn], tot = 0, n, pos = 0;

void add(int x, int y) {
ver[++tot] = y; ne[tot] = head[x]; head[x] = tot;
}

int da[maxn], db[maxn], d[maxn], vis[maxn];

void bfs(int u) {
memset(d, 0, sizeof d);
memset(vis, 0, sizeof vis);
vis[u] = 1; d[u] = 0;
queue<int> q;
q.push(u);

while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;

vis[y] = 1;
d[y] = d[x] + 1;
if (d[y] > d[pos]) pos = y;
q.push(y);
}
}
}

void solve() {
bfs(1);
int a = pos;

bfs(a);
int b = pos;
memcpy(da, d, sizeof d);

bfs(b);
memcpy(db, d, sizeof d);

int c = 0;
for (int i = 1; i <= n; i++) {
if (i == a || i == b) continue;
if (da[i] + db[i] > da[c] + db[c]) c = i;
}
int res = (da[b] + db[c] + da[c]) / 2;
printf("%d\n", res);
printf("%d %d %d\n", a, b, c);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);

// get data
for (int i = 0; i < n-1; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}

solve();
}

  • bfs 求树的直径比较适用于无边权,或者边的权值为11 的情况
  • bfs 求直径很容易求出直径的端点a,ba, b 到树中其他各点的距离

树形 dp 求树的直径

treedp

1
2
3
4
5
6
7
8
9
10
void dp(int x) {
vis[x] = 1;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;
dp(y);
ans = max(ans, d[x] + d[y] + edges[i]);
d[x] = max(d[x], d[y] + edges[i]);
}
}

树的直径的综合应用(一)

Acwing350
Acwing350-01
Acwing350-02
diameter

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
const int maxn = 200000 + 10;
int head[maxn], edges[maxn], ver[maxn], ne[maxn], tot = 1;
int n, K;

void add(int x, int y, int z) {
ver[++tot] = y; edges[tot] = z; ne[tot] = head[x]; head[x] = tot;
}

int vis[maxn], pre[maxn], d[maxn], pos;
void bfs(int u) {
memset(vis, 0, sizeof vis);
memset(pre, 0, sizeof pre);
memset(d, 0, sizeof d);
vis[u] = 1; d[u] = 0;
queue<int> q; q.push(u);

while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;
vis[y] = 1; d[y] = d[x] + edges[i];
pre[y] = i;
if (d[pos] < d[y]) pos = y;
q.push(y);
}
}
}

void dp(int x, int &res) {
vis[x] = 1;
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;
dp(y, res);
res = max(res, d[x] + d[y] + edges[i]);
d[x] = max(d[x], d[y] + edges[i]);
}
}

void solve() {
bfs(1);
int a = pos;

bfs(a);
int ans = 2*(n-1) - (d[pos] - 1);
if (K == 1) {
printf("%d\n", ans);
return;
}

// reverse path
int u = pos;
while (u) {
int e = pre[u];
edges[e] = edges[e^1] = -1;
u = ver[e^1];
}

// dp
memset(vis, 0, sizeof vis);
memset(d, 0, sizeof d);
int L = 0;
dp(1, L);
ans -= (L-1);
printf("%d\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &K);
for (int i = 0; i < n-1; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b, 1);
add(b, a, 1);
}

// then solve
solve();
}

树的直径的综合应用(二)

树网的核
很容易想到一种朴素算法,就是根据树网的核的定义,直接模拟

  • 求出树的直径LL
  • 枚举两个端点[p,q][p, q],保证qp+1sq-p+1 \leqslant s,线段[p,q][p, q] 是树网的核
  • 模拟
    • 对核ker\textbf{ker} 上的每个节点标记vis[ ]=1,D[ ]=d[ ]=0\textbf{vis}[\ ] = 1, D[\ ] = d[\ ] = 0
    • for uker,dfs(u)\textbf{for} \ \forall u \in \bold{ker}, \textbf{dfs}(u) 或者bfs(u)\textbf{bfs}(u)
      dfs\textbf{dfs} 的时候,可以求出核外的点xxuu 的距离d(x)d(x)
      对于边(u,x)(u, x),执行D(x)min{d(u)+e(u,x)}D(x) \leftarrow \min \{d(u) + e(u, x)\}
    • 遍历完成之后,对于ker\textbf{ker} 之外的每个节点xx
      xker\forall x \notin \textbf{ker},此时D(x)D(x) 保存的就是节点xxker\bold{ker} 的距离
      xker\forall x \notin \textbf{ker},对所有的D(x)D(x) 取最小值resres
    • ansmin{res}ans \leftarrow \min \{res\},然后再检查其他的核
      最后ansans 即为所求

Acwing351-01
Acwing351-02
Acwing351-03

编程小 tips
直径的方案可以用一个二元组(id,dist)(id, dist) 来保存到path[]\textbf{path}[\cdots]
方便之后计算

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
102
103
104
105
106
107
108
109
const int maxn = 500000 + 10;
const int maxm = 1000000 + 5;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], edges[maxm], ne[maxm], tot = 1;
int n, s;

void add(int x, int y, int z) {
ver[++tot] = y; edges[tot] = z; ne[tot] = head[x]; head[x] = tot;
}

int vis[maxn], pre[maxn], d[maxn];
void bfs(int u, int &pos) {
memset(vis, 0, sizeof vis);
memset(pre, 0, sizeof pre);
memset(d, 0, sizeof d);
vis[u] = 1; d[u] = 0;
queue<int> q; q.push(u);

while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;
vis[y] = 1;
d[y] = d[x] + edges[i];
pre[y] = x;
if (d[y] > d[pos]) pos = y;
q.push(y);
}
}
}

typedef pair<int, int> PII;
vector<PII> a;

int D[maxn];
int bfs_max(int u) {
vis[u] = 1;
queue<int> q;
q.push(u);

int res = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (vis[y]) continue;
vis[y] = 1;
d[y] = d[x] + edges[i];
if (d[y] > res) res = d[y];
q.push(y);
}
}
return res;
}

void diameter() {
int p = 0;
bfs(1, p);
int q = 0;
bfs(p, q);

while (q) {
a.push_back({q, d[q]});
q = pre[q];
}
reverse(a.begin(), a.end());

// mark diameter
memset(vis, 0, sizeof vis);
for (auto x : a) vis[x.first] = 1;

// get max dist out diameter
memset(d, 0, sizeof d);
for (auto x : a) D[x.first] = bfs_max(x.first);
// for (int i = 1; i <= n; i++) printf("%d\n", D[i]);
}

void solve() {
int q[maxn], l = 1, r = 0, ans = inf;
for (int i = 0, j = 0; i < a.size(); i++) {
while (a[i].second - a[j].second > s) j++;
assert(j <= i);

int res = max(a[j].second - a[0].second, a.back().second - a[i].second);
while (l <= r && q[l] < j) l++;
res = max(res, D[a[q[l]].first]);
ans = min(ans, res);
while (l <= r && D[a[q[r]].first] <= D[a[i].first]) r--;
q[++r] = i;
}
printf("%d\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &s);
for (int i = 0; i < n-1; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c);
}

// then diameter
diameter();

// solve
solve();
}

树的直径的必须边

Acwing389
Acwing389