TIOJ 1214 樹同構

ICPC 2020 Taipei 出了一題水母圖的同構，於是今天找了這題樹同構練習，採用括號字串的方法，而不是 Hashing。

水母圖
- 對於環上每個點當 root 去生出樹字串。
- 串接起來後，用環狀字串的演算法去比較。

TIOJ 1214 - 樹論之樹同構測試

$$O(|G|^2 \log \Delta(G)) = O(n^2 \log n)$$

n ≤ 100。給定兩棵樹的邊，問他們是否同構 “isomorphic”
先 DFS 找出所有的樹重心（最多 2 個）。樹重心的定義為，最大子樹大小最小的點。
從重心開始做 DFS，將每個點用 () 表示，中間夾括入他所有子樹字串，將他們排序後加入。每次排序為度數個，所以總共需要排序 deg - 1 個，所有點加起來為 n 個，再乘上字串比較的複雜度 O(n)。
最後再將重心們的字串排序後串接，比較兩棵樹是否相同。

 1#pragma GCC optimization ("O3")
 2#include<bits/stdc++.h>
 3using namespace std;
 4#define pb push_back
 5int n;
 6int dfs(int u, int p, int &mi, vector<vector<int> > &G, vector<int> &ret) {
 7    int cnt = 0, mx = 0;
 8    for (int uu : G[u]) {
 9        if (uu == p) continue;
10        int r = dfs(uu, u, mi, G, ret);
11        mx = max(mx, r), cnt += r;
12    }
13    mx = max(mx, n - cnt - 1);
14    if (mx <= mi) {
15        if (mx < mi) ret.clear(), mi = mx;
16        ret.pb(u);
17    }
18    return cnt + 1;
19}
20vector<int> centroid(vector<vector<int> > &G) {
21    vector<int> ret;
22    int mi = n;
23    dfs(1, -1, mi, G, ret);
24    return ret;
25}
26string tree(int u, int p, vector<vector<int> > &G) {
27    string ret = "";
28    vector<string> sub;
29    for (int uu : G[u])
30        if (uu != p) sub.pb(tree(uu, u, G));
31    sort(sub.begin(), sub.end());
32    for (string s : sub) ret += s;
33    return "(" + ret + ")";
34}
35string solve() {
36    vector<vector<int> > G(n + 1);
37    for (int i = 1; i < n; i++) {
38        int a, b; cin >> a >> b;
39        G[a].pb(b), G[b].pb(a);
40    }
41    vector<string> ans;
42    for (int u : centroid(G)) ans.pb(tree(u, -1, G));
43    sort(ans.begin(), ans.end());
44    string ret = "";
45    for (string s : ans) ret += s;
46    return ret;
47}
48int main() {
49    ios::sync_with_stdio(0), cin.tie(0);
50    while (1) {
51        cin >> n; if (!n) break;
52        cout << (solve() == solve() ? "Same" : "Different") << '\n';
53    }
54    return 0;
55}

TIOJ 1214 - 樹論 之 樹同構測試

TIOJ 1214 - 樹論之樹同構測試