-
Notifications
You must be signed in to change notification settings - Fork 0
/
centroid-decomposition.cpp
68 lines (57 loc) · 1.81 KB
/
centroid-decomposition.cpp
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
#pragma once
#include <bits/stdc++.h>
using namespace std;
struct CentroidDecomposition {
private:
vector<bool> used;
vector<int> sz;
inline int calc_size(int u, int p) {
sz[u] = 1;
for(int v : tree[u])
if(!used[v] && v != p) sz[u] += calc_size(v, u);
return sz[u];
}
inline int find_centroid(int u, int p, const int mid) {
for(int v : tree[u])
if(!used[v] && v != p && sz[v] > mid)
return find_centroid(v, u, mid);
return u;
}
inline void belong_dfs(int u, int p, int centroid) {
belong[u].push_back(centroid);
for(int v : tree[u])
if(!used[v] && v != p) belong_dfs(v, u, centroid);
}
inline int build(int u) {
int centroid = find_centroid(u, -1, calc_size(u, -1) / 2);
used[centroid] = true;
belong_dfs(centroid, -1, centroid);
for(int v : tree[centroid])
if(!used[v]) cdtree[centroid].push_back(build(v));
used[centroid] = false;
return centroid;
}
public:
vector<vector<int>> tree, cdtree;
vector<vector<int>> belong; // belong[u]: u を含む連結成分の centroid たち
int root = -1; // root of cdtree
explicit CentroidDecomposition(const vector<vector<int>> &g)
: tree(g), root(-1) {}
explicit CentroidDecomposition(int n) : tree(n), root(-1) {}
inline void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
// return root of cdtree
inline int build() {
cdtree.assign(tree.size(), {});
used.assign(tree.size(), false);
sz.resize(tree.size());
belong.assign(tree.size(), {});
return root = build(0);
}
};
/*
* @brief Centroid-Decomposition
* @docs docs/centroid-decomposition.md
*/