Đẳng cấu cây và hash cây (Tree Isomorphism)
Kiểm tra hai cây có cùng hình dạng bằng mã chuẩn AHU trong O(N log N), hash cây ngẫu nhiên chống hack, cây không gốc qua trọng tâm và hash mọi gốc bằng rerooting.
Hai cây được gọi là đẳng cấu (isomorphic) nếu có thể đánh số lại các đỉnh của cây này để nhận được đúng cây kia, tức là chúng có cùng "hình dạng" và chỉ khác nhau ở tên đỉnh. Bài toán: cho hai cây đỉnh, kiểm tra chúng có đẳng cấu không; hoặc cho một cây, đếm xem có bao nhiêu cây con khác hình dạng. Thử mọi hoán vị tốn , còn thuật toán AHU (Aho, Hopcroft, Ullman) gán cho mỗi cây con một mã chuẩn (canonical form) là số nguyên, giải bài trong . Biến thể dùng hash ngẫu nhiên chạy gần và kết hợp được với đổi gốc (rerooting).
Ý tưởng / Trực giác
Cây có gốc: hình dạng chỉ phụ thuộc vào "tập hình dạng của các con"
Với cây có gốc, cây con gốc được xác định hoàn toàn bởi đa tập (multiset) hình dạng của các cây con gốc tại các con của . Thứ tự các con không quan trọng: đổi chỗ hai con vẫn là cùng một cây. Vậy nếu ta có một cách "đặt tên" cho mỗi hình dạng sao cho
với là một song ánh (hai đa tập khác nhau cho hai tên khác nhau), thì bằng quy nạp theo chiều cao: hai cây con đẳng cấu khi và chỉ khi có cùng tên.
- Chiều thuận: nếu hai cây con đẳng cấu, phép đẳng cấu ghép các con của gốc này với các con của gốc kia thành từng cặp đẳng cấu, nên đa tập tên con giống nhau, suy ra tên gốc giống nhau.
- Chiều ngược: nếu tên gốc giống nhau thì (vì là song ánh) đa tập tên con giống nhau; ghép các con cùng tên thành cặp, theo quy nạp mỗi cặp đẳng cấu, ghép các phép đẳng cấu đó lại được phép đẳng cấu của cả cây.
Cách biểu diễn đa tập một cách duy nhất rất đơn giản: sắp xếp danh sách tên các con. Hai đa tập bằng nhau khi và chỉ khi hai danh sách đã sắp bằng nhau.
Mã ngoặc: cách nhìn trực quan
Cách dễ hiểu nhất là cho mỗi cây con một xâu ngoặc: lá là (), đỉnh trong là ( + nối các xâu của con sau khi sắp xếp + ). Đây chính là một song ánh như trên. Nhược điểm: xâu của đỉnh dài , trên cây hình đường thẳng tổng độ dài là .
AHU: nén mỗi xâu thành một số nguyên
AHU làm đúng như mã ngoặc nhưng thay mỗi xâu bằng một số nguyên nhỏ: dùng một từ điển map<vector<int>, int> ánh xạ "danh sách tên con đã sắp" sang một id mới. Lần đầu gặp danh sách nào thì cấp id tiếp theo . Do mỗi đỉnh chỉ góp một số vào danh sách của cha, tổng độ dài mọi danh sách là thay vì .
Quan trọng: hai cây cần so sánh phải dùng chung một từ điển, nếu không cùng hình dạng có thể nhận hai id khác nhau.
Cây không gốc: neo vào trọng tâm
Với cây không gốc, ta cần một đỉnh gốc "chuẩn" mà mọi phép đẳng cấu đều bảo toàn. Đó là trọng tâm (centroid): đỉnh mà khi xoá đi, mọi thành phần còn lại có không quá đỉnh (xem Phân tách trọng tâm). Mỗi cây có 1 hoặc 2 trọng tâm (khi có 2 thì chúng kề nhau), và phép đẳng cấu biến trọng tâm thành trọng tâm. Vậy:
- Tính mã có gốc tại mỗi trọng tâm (tối đa 2 lần AHU).
- Mã của cây không gốc = min các mã đó.
- Hai cây không gốc đẳng cấu khi và chỉ khi mã không gốc bằng nhau.
Ví dụ chạy tay
Ba cây có gốc tại đỉnh 1, mỗi cây 6 đỉnh. :
tree 1 2 1 3 2 4 2 5 3 6 label 1 id=3 label 2 id=2 label 3 id=1 label 4 id=0 label 5 id=0 label 6 id=0
(đánh số khác, các con nằm ở vị trí khác):
tree 1 2 1 3 2 4 3 5 3 6 label 1 id=3 label 2 id=1 label 3 id=2 label 4 id=0 label 5 id=0 label 6 id=0
(cùng số đỉnh, cùng số lá, nhưng hình dạng khác):
tree 1 2 1 3 2 4 4 5 3 6 label 1 id=5 label 2 id=4 label 3 id=1 label 4 id=1 label 5 id=0 label 6 id=0
Xử lý lần lượt , , với chung một từ điển, mỗi cây duyệt theo thứ tự BFS ngược (con luôn xong trước cha):
| Cây | Đỉnh | Danh sách id con (đã sắp) | Có trong từ điển? | id |
|---|---|---|---|---|
| 6, 5, 4 | () |
chưa, thêm () -> 0 |
0 | |
| 3 | (0) |
chưa, thêm (0) -> 1 |
1 | |
| 2 | (0, 0) |
chưa, thêm (0,0) -> 2 |
2 | |
| 1 | (1, 2) |
chưa, thêm (1,2) -> 3 |
3 | |
| 6, 5, 4 | () |
có | 0 | |
| 3 | (0, 0) |
có | 2 | |
| 2 | (0) |
có | 1 | |
| 1 | (2, 1) sắp thành (1, 2) |
có | 3 | |
| 5, 6 | () |
có | 0 | |
| 4 | (0) |
có | 1 | |
| 3 | (0) |
có | 1 | |
| 2 | (1) |
chưa, thêm (1) -> 4 |
4 | |
| 1 | (1, 4) |
chưa, thêm (1,4) -> 5 |
5 |
Kết luận: nên ; nên khác hình dạng. Bước then chốt là ở gốc của : danh sách (2, 1) phải sắp xếp thành (1, 2) mới khớp với .
So sánh với mã ngoặc: và đều cho ((()())(())), còn cho (((()))(())).
Trường hợp hai trọng tâm. Đường thẳng 4 đỉnh có hai trọng tâm là 2 và 3 (xoá đỉnh nào cũng để lại phần lớn nhất 2 đỉnh ):
tree 1 2 2 3 3 4 highlight orange 2 3 label 2 trọng tâm label 3 trọng tâm
Nếu chỉ lấy "một trọng tâm bất kỳ", cây này có thể chọn 2 còn bản đánh số lại của nó chọn 3. Ở ví dụ này hai cách treo cho cùng hình dạng, nhưng nói chung (ví dụ cây "chổi" lệch hai bên cạnh nối hai trọng tâm) hai cách treo cho hai id khác nhau, nên phải tính cả hai và lấy min.
Cài đặt
AHU: kiểm tra hai cây không gốc đẳng cấu
Input: , rồi cạnh của cây thứ nhất, rồi cạnh của cây thứ hai. In YES nếu đẳng cấu, ngược lại NO. Cả hai bản đều duyệt không đệ quy (BFS rồi xử lý theo thứ tự ngược) nên chạy được cây hình đường thẳng đỉnh.
#include <bits/stdc++.h>
using namespace std;
// Shared dictionary: sorted list of child ids -> id of the shape.
// MUST be shared between both trees so equal shapes get equal ids.
map<vector<int>, int> shapeId;
// Canonical id of the tree rooted at <!--LCODE30--> (AHU), iterative.
int rootedId(int n, const vector<vector<int>>& adj, int root) {
vector<int> order, par(n + 1, 0), id(n + 1);
order.reserve(n);
order.push_back(root);
par[root] = -1;
for (int i = 0; i < (int)order.size(); i++) { // BFS order
int u = order[i];
for (int v : adj[u])
if (v != par[u]) { par[v] = u; order.push_back(v); }
}
vector<vector<int>> kids(n + 1);
// Reverse BFS order: every child is finished before its parent
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
vector<int>& k = kids[u];
sort(k.begin(), k.end()); // order of children does not matter
auto it = shapeId.find(k);
if (it == shapeId.end()) it = shapeId.emplace(k, (int)shapeId.size()).first;
id[u] = it->second;
if (par[u] != -1) kids[par[u]].push_back(id[u]);
vector<int>().swap(k); // free memory early
}
return id[root];
}
// 1 or 2 centroids of a tree
vector<int> centroids(int n, const vector<vector<int>>& adj) {
vector<int> order, par(n + 1, 0), sz(n + 1, 1);
order.push_back(1);
par[1] = -1;
for (int i = 0; i < (int)order.size(); i++) {
int u = order[i];
for (int v : adj[u])
if (v != par[u]) { par[v] = u; order.push_back(v); }
}
vector<int> res;
for (int i = n - 1; i >= 0; i--) {
int u = order[i], biggest = 0;
for (int v : adj[u])
if (v != par[u]) { sz[u] += sz[v]; biggest = max(biggest, sz[v]); }
biggest = max(biggest, n - sz[u]); // the part above u
if (2 * biggest <= n) res.push_back(u);
}
return res;
}
// Unrooted canonical form: the smallest id over all centroids
int unrootedId(int n, const vector<vector<int>>& adj) {
int best = INT_MAX;
for (int c : centroids(n, adj)) best = min(best, rootedId(n, adj, c));
return best;
}
int main() {
int n;
scanf("%d", &n);
vector<vector<int>> a(n + 1), b(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; scanf("%d %d", &u, &v);
a[u].push_back(v); a[v].push_back(u);
}
for (int i = 0; i < n - 1; i++) {
int u, v; scanf("%d %d", &u, &v);
b[u].push_back(v); b[v].push_back(u);
}
puts(unrootedId(n, a) == unrootedId(n, b) ? "YES" : "NO");
}
import sys
def rooted_id(n, adj, root, shape_id):
# BFS order (iterative, no recursion limit issues)
par = [0] * (n + 1)
par[root] = -1
order = [root]
for u in order:
for v in adj[u]:
if v != par[u]:
par[v] = u
order.append(v)
kids = [[] for _ in range(n + 1)]
ids = [0] * (n + 1)
for u in reversed(order): # children are finished before parents
key = tuple(sorted(kids[u])) # order of children does not matter
if key not in shape_id:
shape_id[key] = len(shape_id)
ids[u] = shape_id[key]
if par[u] != -1:
kids[par[u]].append(ids[u])
kids[u] = None # free memory early
return ids[root]
def centroids(n, adj):
par = [0] * (n + 1)
par[1] = -1
order = [1]
for u in order:
for v in adj[u]:
if v != par[u]:
par[v] = u
order.append(v)
sz = [1] * (n + 1)
res = []
for u in reversed(order):
biggest = 0
for v in adj[u]:
if v != par[u]:
sz[u] += sz[v]
biggest = max(biggest, sz[v])
biggest = max(biggest, n - sz[u]) # the part above u
if 2 * biggest <= n:
res.append(u)
return res
def unrooted_id(n, adj, shape_id):
# smallest id over the 1 or 2 centroids
return min(rooted_id(n, adj, c, shape_id) for c in centroids(n, adj))
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
pos = 1
trees = []
for _ in range(2):
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = int(data[pos]), int(data[pos + 1])
pos += 2
adj[u].append(v)
adj[v].append(u)
trees.append(adj)
shape_id = {} # shared between both trees
a = unrooted_id(n, trees[0], shape_id)
b = unrooted_id(n, trees[1], shape_id)
print("YES" if a == b else "NO")
main()
Với input là và ở trên (6, các cạnh 1 2, 1 3, 2 4, 2 5, 3 6, rồi 1 2, 1 3, 2 4, 3 5, 3 6), cả hai bản in YES.
Hash cây ngẫu nhiên: đếm cây con khác nhau và hash mọi gốc
Thay từ điển bằng một hàm hash có tính giao hoán theo các con:
trong đó mix là hàm trộn bit mạnh (splitmix64) cộng thêm một seed ngẫu nhiên lúc chạy. Phép cộng không phụ thuộc thứ tự con nên không cần sắp xếp. Đổi lại, kết quả chỉ đúng với xác suất rất cao (va chạm khoảng ), không phải chắc chắn như AHU.
Vì là tổng nên có thể "trừ bớt" một con, nhờ đó tính được hash của cả cây khi treo tại mọi gốc bằng đổi gốc (rerooting): với là con của ,
Chương trình dưới đây đọc một cây, in số cây con đôi một không đẳng cấu (gốc 1) và số cách treo gốc cho ra hình dạng khác nhau. Với kết quả là 4 5 (cây con: lá, đỉnh 3, đỉnh 2, cả cây; treo tại 4 hay 5 cho cùng hình dạng).
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
// Random seed chosen at run time: test data cannot be prepared against it
const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
// splitmix64: strong bit mixing, applied to every child hash
ull mix(ull x) {
x += 0x9e3779b97f4a7c15ULL + SEED;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
int main() {
int n;
scanf("%d", &n);
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; scanf("%d %d", &u, &v);
adj[u].push_back(v); adj[v].push_back(u);
}
// BFS order from root 1
vector<int> order = {1}, par(n + 1, 0);
for (int i = 0; i < (int)order.size(); i++) {
int u = order[i];
for (int v : adj[u])
if (v != par[u]) { par[v] = u; order.push_back(v); }
}
// down[v] = 1 + sum mix(down[child]) (unsigned overflow = mod 2^64)
vector<ull> down(n + 1, 1);
for (int i = n - 1; i > 0; i--) {
int u = order[i];
down[par[u]] += mix(down[u]);
}
// Number of pairwise non-isomorphic subtrees (tree rooted at 1)
set<ull> subtrees(down.begin() + 1, down.end());
// Rerooting: full[v] = hash of the WHOLE tree when rooted at v
vector<ull> full(n + 1);
full[1] = down[1];
for (int i = 1; i < n; i++) {
int c = order[i], p = par[c];
ull upPart = full[p] - mix(down[c]); // p's side, with c's branch removed
full[c] = down[c] + mix(upPart);
}
set<ull> roots(full.begin() + 1, full.end());
printf("%d %d\n", (int)subtrees.size(), (int)roots.size());
}
import sys
import random
MASK = (1 << 64) - 1
SEED = random.getrandbits(64) # chosen at run time, cannot be hacked in advance
def mix(x):
# splitmix64 on 64-bit unsigned integers
x = (x + 0x9E3779B97F4A7C15 + SEED) & MASK
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
return x ^ (x >> 31)
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
adj[u].append(v)
adj[v].append(u)
par = [0] * (n + 1)
order = [1]
for u in order: # BFS order from root 1
for v in adj[u]:
if v != par[u]:
par[v] = u
order.append(v)
# down[v] = 1 + sum mix(down[child]) (mod 2^64)
down = [1] * (n + 1)
for u in reversed(order[1:]):
down[par[u]] = (down[par[u]] + mix(down[u])) & MASK
subtrees = len(set(down[1:])) # non-isomorphic subtrees (root 1)
# Rerooting: full[v] = hash of the whole tree rooted at v
full = [0] * (n + 1)
full[1] = down[1]
for c in order[1:]:
p = par[c]
up_part = (full[p] - mix(down[c])) & MASK # p's side without c's branch
full[c] = (down[c] + mix(up_part)) & MASK
roots = len(set(full[1:]))
print(subtrees, roots)
main()
Cả bốn chương trình đã được đối chiếu với brute force (thử mọi hoán vị với , so mã ngoặc với ) trên hàng trăm cây ngẫu nhiên, và chạy dưới 1 giây với đường thẳng đỉnh.
Độ phức tạp
- AHU, thời gian . Tổng độ dài mọi danh sách con là (mỗi đỉnh nằm trong danh sách của đúng một cha). Sắp danh sách của tốn . Một lần tra
mapthực hiện phép so sánh vector, mỗi phép so sánh tốn tối đa , nên đỉnh tốn . Cộng lại . Cây không gốc chỉ chạy AHU tối đa 2 lần mỗi cây (2 trọng tâm), không đổi bậc độ phức tạp. - AHU, bộ nhớ . Từ điển chứa tối đa khoá với tổng độ dài cho mỗi cây; mảng
order,par,id,kidsđều . - Hash, thời gian để tính mọi (mỗi cạnh gọi
mixmột lần), cộng nếu dùngsetđể đếm giá trị khác nhau (hoặc sắp mảng rồi đếm). Đổi gốc thêm : mỗi cạnh xử lý một lần theo thứ tự BFS. - Hash, bộ nhớ .
- Mã ngoặc dạng xâu: trong trường hợp xấu (cây đường thẳng), chỉ dùng để hiểu hoặc khi rất nhỏ.
⚠️ Lỗi thường gặp
- Đệ quy quá sâu. Cây đường thẳng đến đỉnh làm DFS đệ quy tràn stack trong C++ (Runtime Error) và vượt
recursionlimittrong Python. Cách tránh: lấy thứ tự BFS rồi xử lý ngược thứ tự đó như code mẫu, con luôn được xử lý trước cha. - Quên trường hợp hai trọng tâm. Chọn "trọng tâm đầu tiên tìm thấy" thì hai bản đánh số lại của cùng một cây có thể treo ở hai trọng tâm khác nhau, cho hai mã khác nhau, trả lời
NOsai. Luôn tính mã tại mọi trọng tâm (1 hoặc 2) và lấy min (hoặc so sánh tập mã). - Mỗi cây dùng một từ điển riêng. Id chỉ có nghĩa trong cùng một từ điển: cây thứ nhất có thể gán
(0) -> 1, cây thứ hai riêng lại gán(0,0) -> 1. Mọi cây cần so sánh phải dùng chungshapeId. - Quên sắp xếp danh sách con. Không sắp thì
(2, 1)và(1, 2)thành hai khoá khác nhau, tức là coi thứ tự con là quan trọng; khi đó và ở ví dụ bị coi là khác nhau. - Hash yếu bị hack. Một số công thức nhìn hợp lý nhưng sai hoặc dễ bị dựng test phá:
- (không trộn bit) chính là kích thước cây con, mọi cây cùng số đỉnh đều trùng hash.
- (XOR): hai con giống nhau triệt tiêu nhau, cây có hai nhánh giống hệt bị coi như không có nhánh nào.
- Hash đa thức trên danh sách con đã sắp với cơ số và modulo cố định, công khai: người ra đề (hoặc người hack trên Codeforces) có thể dựng sẵn hai cây khác nhau cùng hash. Cách tránh: dùng hàm trộn mạnh (splitmix64), seed ngẫu nhiên lúc chạy, modulo hoặc hai modulo lớn; khi cần chắc chắn 100% thì dùng AHU.
- Tưởng so sánh vector là . Mỗi phép so sánh khoá trong
map<vector<int>,int>tốn . Tổng vẫn ổn vì tổng độ dài là , nhưng nếu khoá là xâu ngoặc đầy đủ thay vì danh sách id thì độ dài khoá là và tổng thành , TLE với . - Dùng
unordered_mapvới khoá vector mà không tự viết hash. C++ không có sẵnstd::hash<vector<int>>, code không biên dịch; tự viết hash đơn giản thì lại dễ bị anti-hash test.maplà lựa chọn an toàn. - Trường hợp biên và . Với không có cạnh nào, trọng tâm là đỉnh 1; với cả hai đỉnh đều là trọng tâm. Code mẫu xử lý đúng vì điều kiện
2 * biggest <= n.
Biến thể / Mở rộng
- Đếm / nhóm các cây con đẳng cấu. Sau khi chạy AHU (hoặc hash) một lần từ gốc, số giá trị
id[v]khác nhau chính là số loại cây con; gom các đỉnh cùngidđể trả lời "có bao nhiêu cây con giống cây con của ". Đây là dạng hay gặp nhất trong đề thi. - Hash mọi gốc bằng rerooting. Như code thứ hai: tính cho mọi trong , dùng để tìm các gốc cho cùng hình dạng (gốc "đối xứng"), hoặc kiểm tra đẳng cấu không gốc mà không cần tìm trọng tâm (so tập hoặc của hai cây). Kỹ thuật này dựa trên đổi gốc.
- Cây có nhãn / có trọng số cạnh. Đưa nhãn vào khoá: khoá của là
(nhãn(v), danh sách (trọng số cạnh, id con) đã sắp). Với hash, thay bằng hoặc trộn thêm nhãn. - Cây con có thứ tự (ordered tree). Nếu thứ tự con có ý nghĩa thì không sắp xếp danh sách con, khi đó dùng hash xâu thông thường trên dãy id con (xem Hash xâu).
- Đẳng cấu đồ thị tổng quát khó hơn nhiều (chưa biết thuật toán đa thức); kỹ thuật trên chỉ dùng được vì cây phân rã được theo gốc/trọng tâm.
- Hash đa tập nói chung: ý tưởng "cộng với seed ngẫu nhiên" dùng được cho mọi bài cần so sánh hai đa tập nhanh, ví dụ so tập kề của hai đỉnh trong đồ thị.
Bài tập luyện
- Tìm trọng tâm cây (treecent): (Trung bình) cài đúng hàm tìm trọng tâm bằng kích thước cây con, bước đầu tiên của kiểm tra đẳng cấu cây không gốc.
- Đẳng cấu cây I (treeiso1): (Khó) kiểm tra hai cây có gốc (gốc là đỉnh ) có đẳng cấu không, nhiều bộ test. Áp dụng thẳng AHU hoặc hash cây trên gốc cố định.
- Kay và Bông Tuyết (snowflake): (Rất khó) tìm trọng tâm của mọi cây con với , phải duyệt không đệ quy, cần khi muốn so hình dạng không gốc của từng cây con.
- Đẳng cấu cây II (treeiso2): (Rất khó) bản không gốc của bài trên: neo mỗi cây vào hoặc trọng tâm rồi so mã chuẩn, chính là chương trình AHU ở mục Cài đặt, chỉ cần bọc thêm vòng lặp đọc bộ dữ liệu.
- Cây bất biến (invartree): (Rất khó) dựng một cây nhận hoán vị cho trước làm tự đẳng cấu. Mấu chốt là mọi tự đẳng cấu đều giữ nguyên tâm của cây (một đỉnh hoặc một cạnh), cùng ý với bước neo trọng tâm.
- Cặp song trùng (doubprof): (Chuyên gia) so sánh tập kề của đỉnh bằng hash đa tập ngẫu nhiên, đúng ý tưởng "cộng/XOR giá trị ngẫu nhiên, seed lúc chạy" của hash cây.
Bình luận