Subway (树中心 + 树hash)

首先找到树的中心或者中心,我这里是找中心,因为我们需要找一个相同的起点,然后最多2个中心就是树的宽度为偶数时,奇数时为1个。

找到之后需要对树进行hash,使得每个点都具备独特性,使之树的形态能够保证唯一,然后利用hash值,对树的每个节点下的节点进行排序,之后如果判定这两个树是一样的话,我只需要对树进行一次深搜并把遍历的顺序存进数组。然后直接按照数组中的值输出原来映射的字符串就好了。

#include<bits/stdc++.h>
#define LL long long
using namespace std; const int mod = 1e9 + ;
const int maxn = 1e5 + ;
const int seed = ;
char inp[], onp[]; struct Tree{
map<string, int>id;
vector<int>edge[maxn];
string anw[maxn], rip[maxn];
int _cnt, ctr[], siz[maxn], dep[maxn], fa[maxn];
LL Har[maxn]; ///将遍历顺序存进去
void done(int st, int fa){
if(fa == ) _cnt = ;
anw[_cnt ++] = rip[st];
for(auto x : edge[st]){
if(x == fa) continue;
done(x, st);
}
} ///hash技术
LL dfsh(int st, int fa){
Har[st] = seed;siz[st] = ;
for(auto x : edge[st]){
if(x == fa) continue;
dfsh(x, st);
siz[st] += siz[x];
}
sort(edge[st].begin(), edge[st].end(),
[&](int x, int y){return Har[x] < Har[y];});
for(auto x : edge[st]){
if(x == fa) continue;
Har[st] = (((Har[st] * Har[x]) % mod) ^ Har[x])% mod;
}
Har[st] = (Har[st] + siz[st]) % mod;
Har[st] = (Har[st] * Har[st]) % mod;
return Har[st];
} ///得到深度值
void getdep(int st, int Fa, int Dep){
dep[st] = Dep;fa[st] = Fa;
for(auto x : edge[st]){
if(x == fa[st]) continue;
getdep(x,st,Dep + );
}
} ///获取中点
void getCtr(int n){
getdep(, , );
ctr[] = max_element(dep + , dep + + n) - dep;
getdep(ctr[], , );
ctr[] = max_element(dep + , dep + + n) - dep;
int fdep = dep[ctr[]];
for(int i = ; i < fdep/; i ++)
ctr[] = fa[ctr[]];
ctr[] = ctr[];
if(fdep & ) ctr[] = fa[ctr[]];
} ///重置数据
void init(int n){
for(int i = ; i <= n; i ++)
edge[i].clear();
id.clear();_cnt = ;
} ///映射连接的符号,并存进对应的map值为下标的地方
int toid(string v){
if(id.find(v) != id.end()) return id[v];
rip[_cnt] = v;
return id[v] = _cnt ++;
} ///建图,映射值
void input(int n){
init(n);int l,r;
for(int i = ; i < n; i ++){
scanf("%s %s", inp, onp);
l = toid(inp); r = toid(onp);
edge[l].push_back(r);
edge[r].push_back(l);
}
}
}X, Y; void solve(){
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
if(X.dfsh(X.ctr[i], ) == Y.dfsh(Y.ctr[j], )){
X.done(X.ctr[i], );
Y.done(Y.ctr[j], );
return;
}
} int main(){
int n;while(~scanf("%d", &n)){
X.input(n);
Y.input(n);
X.getCtr(n);
Y.getCtr(n);
solve();
for(int i = ; i < n; i ++)
printf("%s %s\n",X.anw[i].c_str(), Y.anw[i].c_str());
}return ;
}

这次的代码可以说是照搬过来的,菜鸡的自己。

上一篇:Volley网络通信框架


下一篇:python中map()和dict()的用法