[TIOJ] 1214. 樹論 之 樹同構測試 (確定性作法)
題目連結:http://tioj.infor.org/problems/1214
前面稍微講了一下用hash的作法,不過當參數取的不好時,hash是很有可能會撞的。如果一定要確定性的算法的話,可以把hash作法改成:對於葉節點先定義一個值,而對於非葉節點則蒐集起他所有子樹的hash值排序好後塞到map之類的容器並訂一個值(例如直接用map的size),那這樣複雜度會退化成$O(nlogn)$但是就不會有碰撞的問題了。
前面稍微講了一下用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
留言
張貼留言