blob: f3e147b8a8f6829f6f24074050459266fedd1689 (
plain)
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
|
vector<vector<vector<int>>>
getTreeLabel(const vector<vector<int>>& adj, int root) {
vector<vector<int>> level = {{root}};
vector<int> dist(sz(adj), -1);
dist[root] = 0;
queue<int> q;
q.push(root);
while (!q.empty()) {
int c = q.front();
q.pop();
for (int n : adj[c]) {
if (dist[n] < 0) {
dist[n] = dist[c] + 1;
if (sz(level) <= dist[n]) level.push_back({});
level[dist[n]].push_back(n);
q.push(n);
}}}
vector<vector<vector<int>>> levelLabels(sz(level));
vector<int> shortLabel(sz(adj));
for (int l = sz(level) - 1; l >= 0; l--) {
vector<pair<vector<int>, int>> tmpLabels;
for (int v : level[l]) {
vector<int> label;
for (int n : adj[v]) {
if (dist[n] > dist[v]) {
label.push_back(shortLabel[n]);
}}
sort(all(label));
tmpLabels.push_back({label, v});
}
sort(all(tmpLabels));
vector<int>& last = tmpLabels[0].first;
int curId = 0;
for (auto& e : tmpLabels) {
levelLabels[l].push_back(e.first);
if (e.first != last) curId++, last = e.first;
shortLabel[e.second] = curId;
}}
return levelLabels;
}
|
