【題解】TIOJ 1214 . 樹論 之 樹同構測試

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxn = 105;
const int mul = 37;
const int mod = 1e9+7;
vector <int> g[2][maxn];

int dfs(int now, int pre, int idx){
    vector <int> v;
    for (auto nxt: g[idx][now]){
        if (nxt == pre) continue;
        v.push_back(dfs(nxt, now, idx));
    }
    sort(v.rbegin(), v.rend()); //由大排到小，避免碰撞
    long long ret = 1; //如果是葉節點，會回傳 1
    for (auto i: v){
        ret *= mul;
        ret += i;
        ret %= mod;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, x, y;
    while (cin >> n){
        if (n == 0) break;
        for (int i=0; i<=n; i++){
            g[0][i].clear();
            g[1][i].clear();
        }
        for (int i=0; i<n-1; i++){
            cin >> x >> y;
            g[0][x].push_back(y);
            g[0][y].push_back(x);
        }
        set <int> st; //紀錄第一棵樹所有可能的hash值
        for (int i=1; i<=n; i++){
            st.insert(dfs(i, 0, 0));
        }
        for (int i=0; i<n-1; i++){
            cin >> x >> y;
            g[1][x].push_back(y);
            g[1][y].push_back(x);
        }
        if (st.count(dfs(1, 0, 1))) cout << "Same\n";
        else cout << "Different\n";
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, a, b;
int mul = 37, mod = 1e9+7;
int hash1; //第一棵樹，以mid[1]為root的hash值
int hash2[2]; //第二棵樹，以mid[1]/mid[2]為root的hash值
int mid[3]; //0:目前找到最長的路徑, 1/2: 路徑上的中心點
int d[105]; //每個節點的depth
vector <int> tree[105];

int dfs_depth(int now, int pre){
    d[now] = d[pre]+1;
    if (tree[now].size() == 1 && tree[now][0] == pre){
        return now;
    }
    int idx = 0, num;
    for (int i:tree[now]){
        if (i == pre) continue;
        num = dfs_depth(i, now);
        if (d[num] > d[idx]){
            idx = num;
        }
    }
    if (d[idx] > mid[0] && d[now] == d[idx]/2+1){
        mid[0] = d[idx];
        if (d[idx] % 2 != 0){
            mid[1] = now;
            mid[2] = 0;
        }
        else{
            mid[1] = now;
            mid[2] = pre;
        }
    }
    return idx;
}

int dfs_hash(int now, int pre){
    if (now != 1 && tree[now].size() == 1){
        return 1;
    }
    vector <int> v;
    for (int i:tree[now]){
        if (i == pre) continue;
        v.push_back(dfs_hash(i, now));
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    long long ret = 1;
    for (int i:v){
        ret *= mul;
        ret += i;
        ret %= mod;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n){
        if (n == 0) break;
        else if (n == 1){
            cout << "Same\n";
            continue;
        }
        else if (n == 2){
            cin >> a >> b;
            cin >> a >> b; //把input data讀完
            cout << "Same\n";
            continue;
        }
        for (int i = 1; i <= n; i++){
            tree[i].clear();
        }
        for (int i = 1; i < n; i++){
            cin >> a >> b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        mid[0] = 0;
        int num = dfs_depth(1, 0);
        dfs_depth(num, 0);
        hash1 = dfs_hash(mid[1], 0);

        for (int i = 1; i <= n; i++){
            tree[i].clear();
        }
        for (int i = 1; i < n; i++){
            cin >> a >> b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        
        mid[0] = 0;
        num = dfs_depth(1, 0);
        dfs_depth(num, 0);
        hash2[0] = dfs_hash(mid[1], 0);
        if (mid[2] != 0) hash2[1] = dfs_hash(mid[2], 0);
        else hash2[1] = 0;

        if (hash1 == hash2[0] || hash1 == hash2[1]) cout << "Same\n";
        else cout << "Different\n";
    }
}