首页 > 代码库 > ZOJ 3602 Count the Trees 树的同构 （哈希）
ZOJ 3602 Count the Trees 树的同构 （哈希）
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4705
题意：给出两棵二叉树A和B，问分别处于A中的子树a和处于B中的子树b结构相同的有多少对。
思路：哈希的想法，不同的数字对应的是不同的结构，比如1代表着单独的叶子结点，2代表着有左子树是叶子结点而没有右子树的子树...每出现一种新的子树情形就记录下来，记录的方式是用dfs回溯过程中判断左子树和右子树组成的子树是否出现过（用pair记录子树的情况，也就是左右子树，两个map，第一个map表示子树的pair与它的标号的映射，第二个map表示每种标号出现的次数）。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int top=0;
map < pair < int , int > , int > M;
map < int , LL > N ;
int tree_a[maxn][2],tree_b[maxn][2],a[maxn],b[maxn];
LL ans;
void dfs_a(int u)
{
pair < int , int > p;
int left,right;
left=tree_a[u][0],right=tree_a[u][1];
if(left!=-1)
dfs_a(left);
if(right!=-1)
dfs_a(right);
if(left==-1)
p.first=-1;
else p.first=a[left];
if(right==-1)
p.second=-1;
else p.second=a[right];
if(M.find(p)==M.end())
{
M[p]=top;
a[u]=top;
N[top]=1;
top+=3;
}
else
{
a[u]=M[p];
N[M[p]]++;
}
}
void dfs_b(int u)
{
pair <int ,int > p ;
int left=tree_b[u][0],right=tree_b[u][1];
if(left!=-1)
dfs_b(left);
if(right!=-1)
dfs_b(right);
if(left==-1)
p.first=-1;
else p.first=b[left];
if(right==-1)
p.second=-1;
else p.second=b[right];
if(M.find(p)!=M.end())
{
ans+=N[M[p]];
b[u]=M[p];
}
}
void init()
{
top=0;
ans=0;
N.clear();
M.clear();
for(int i=0;i<=100000;i++)
a[i]=-2,b[i]=-2;
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d%d",&tree_a[i][0],&tree_a[i][1]);
for(int i=1; i<=m; i++)
scanf("%d%d",&tree_b[i][0],&tree_b[i][1]);
dfs_a(1);
dfs_b(1);
printf("%lld\n",ans);
}
return 0;
}
ZOJ 3602 Count the Trees 树的同构 （哈希）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。