首页 > 代码库 > ZOJ--3602--Count the Trees【DFS+Hash】树的同构
ZOJ--3602--Count the Trees【DFS+Hash】树的同构
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3602
题意：给出一棵有n个节点的二叉树和一棵有m个节点的二叉树，给出每个节点的左右子树信息，问这两棵树有几个相同的子树。
思路：树的同构，比赛时没想法，赛后看的别人的解题报告。实际上是给每个节点的左右子树一个哈希值，不用像字符串哈希那么麻烦，直接给每个子树一个数字标记就行了，用map映射每个节点的左子树和右子树信息对应一个标记值，用DFS给两棵树的每个节点都赋一个哈希值。赋完之后判断第一个树每个节点和第二个树每个节点的哈希值，如果相等则答案+1，不过节点数太大，这么遍历是时间复杂度是100000*100000，会TLE，用一个新的map记录第一个数的所有哈希值，再在第二个树中判断如果第二个树节点在这个map中存在映射，则答案加这个映射对应的值，这样复杂度是2*100000，不会TLE。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 10100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct node{
int u,v;
}a[101000],b[101000];
int n,m,cnt;
int ans1[101000],ans2[101000];
map<pair<int,int>,int>mp;
void dfs(int u,node c[],int ans[]){
if(c[u].u==-1) ans[c[u].u] = -1;
else dfs(c[u].u,c,ans);
if(c[u].v==-1) ans[c[u].v] = -1;
else dfs(c[u].v,c,ans);
pair<int,int> p = make_pair(ans[c[u].u],ans[c[u].v]);
if(mp.find(p)!=mp.end()) ans[u] = mp[p];
else{
mp[p] = cnt++;
ans[u] = mp[p];
}
}
int main(){
int t,i,j,u,v;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
cnt = 0;
mp.clear();
for(i=1;i<=n;i++){
scanf("%d%d",&a[i].u,&a[i].v);
}
for(i=1;i<=m;i++){
scanf("%d%d",&b[i].u,&b[i].v);
}
dfs(1,a,ans1);
dfs(1,b,ans2);
map<int,int>fuck;
ll ans = 0;
for(i=1;i<=n;i++){
fuck[ans1[i]]++;
}
for(i=1;i<=m;i++){
ans += fuck[ans2[i]];
}
printf("%lld\n",ans);
}
return 0;
}
ZOJ--3602--Count the Trees【DFS+Hash】树的同构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。