[TIOJ] 1214. 樹論 之 樹同構測試 (確定性作法)

題目連結:http://tioj.infor.org/problems/1214

---

前面稍微講了一下用hash的作法，不過當參數取的不好時，hash是很有可能會撞的。如果一定要確定性的算法的話，可以把hash作法改成:對於葉節點先定義一個值，而對於非葉節點則蒐集起他所有子樹的hash值排序好後塞到map之類的容器並訂一個值(例如直接用map的size)，那這樣複雜度會退化成$O(nlogn)$但是就不會有碰撞的問題了。

1214. 樹論 之 樹同構測試 4 1272 Accepted 100
Testdata no.	Time (ms)	Memory (KiB)	Verdict
0	4	1272	Accepted
Submitter: ototot Compiler: c++11 Code Length: 1.77 KB
#include <bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
const int N = 100 + 5;

vector<int> G1[N], G2[N];
int sz1[N], sz2[N];
map<vector<int>,int> bkt;

inline void init(int);
int GetCentroid(vector<int>[],int[],int,int,int);
int Hash(vector<int>[],int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		init(n);
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G1[u].PB(v);
			G1[v].PB(u);
		}
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G2[u].PB(v);
			G2[v].PB(u);
		}
		int cen1 = 1;
		GetCentroid(G1, sz1, 1, 1, n);
		for(int i=1;i<=n;i++) if(sz1[cen1] > sz1[i]) 
			cen1 = i;
		GetCentroid(G2, sz2, 1, 1, n);
		int cen2 = 1;
		for(int i=1;i<=n;i++) if(sz2[cen2] > sz2[i]) 
			cen2 = i;
		int cen22 = cen2;
		for(int i=1;i<=n;i++) if(sz2[cen22] >= sz2[i]) 
			cen22 = i;
		int hh1 = Hash(G1, cen1, cen1);
		int hh2 = Hash(G2, cen2, cen2);
		int hh22 = Hash(G2, cen22, cen22);
		if(hh1 == hh2 or hh1 == hh22) cout<<"Same\n";
		else cout<<"Different\n";
	}
	return 0;
}

inline void init(int n){
	for(int i=1;i<=n;i++){
		G1[i].clear();
		G2[i].clear();
	}
	bkt.clear();
}

int GetCentroid(vector<int> G[], int sz[], int w ,int f, int n){
	int cnt = 1, mx = 0;
	for(auto i: G[w]){
		if(i==f) continue;
		int tp = GetCentroid(G, sz, i, w, n);
		mx = max(tp, mx);
		cnt+=tp;
	}
	mx = max(n-cnt, mx);
	sz[w]=mx;
	return cnt;
}

int Hash(vector<int> G[], int w, int f){
	vector<int> sub;
	for(auto i:G[w]){
		if(i==f) continue;
		sub.PB(Hash(G, i, w));
	}
	sort(ALL(sub));
	auto it = bkt.find(sub);
	if(it==bkt.end()){
		bkt.insert({sub, bkt.size()});
		return bkt.size()-1;
	}else return it->SS;
}p