【範例】Hash，樹圓心
【題目敘述】https://tioj.ck.tp.edu.tw/problems/1214
【方法1】比較不同root的hash值
- 第一棵樹，輪流用每一個節點當作root，對樹進行hash (搭配 DFS)，紀錄於set。
- 第二棵樹，用任一節點當作root，計算hash值。如果此值曾經出現在第一棵樹計算的結果中，則表示兩棵樹同構。
#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;
}
【方法2】找出樹圓心，再進行hash (速度比【方法1】快很多)
- 用兩次DFS找出樹的直徑，直徑的中點即為樹圓心(可能有兩個)。
- 把樹圓心當作root，對樹進行hash (搭配 DFS)。
#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";
}
}