题解 P5043 【【模板】树同构([BJOI2015]树的同构)】
2024-10-08 15:55:27
进入正题
题意:将所有树结构相同的树归类。
思路
嗯,这道题让我们把树的结构归类,自然而然就想到了哈希,我们对这整颗树哈希一遍。然后判同构就十分之简单了。只需要找哈希值一样的树就可以了。
其实真得很简单,不知道为什么是紫的。如果思路还不懂的话,可以看代码注释。
代码
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1001;
long long ans[maxn][maxn],n,m,head[maxn],last[maxn],Next[maxn],tot,x;
void add(int x,int y){ //建边
last[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
long long Hash(int x,int f) //树哈希
{
long long q[maxn],ans=maxn,top=0;
for(int i=head[x];i;i=Next[i]) //遍历所以子节点
if(last[i]!=f) //不能再次遍历以遍历的点,即x的父亲
q[++top]=Hash(last[i],x);
sort(q+1,q+top+1); //把哈希打得更乱
for(int i=1;i<=top;i++) //对x点计算哈希值
ans=ans*2333+q[i];
return ans*2333+maxn+1;
}
int main(){
cin>>m;
for(int i=1;i<=m;i++)
{
tot=0;memset(head,0,sizeof(head)); //建边清0
cin>>n;
for(int j=1;j<=n;j++)
{
cin>>x;
if(x!=0)add(x,j),add(j,x);
}
for(int j=1;j<=n;j++)
ans[i][j]=Hash(j,0); //树哈希
sort(ans[i]+1,ans[i]+n+1);
for(int j=1,k=0;j<=i;j++)
{
while(k<=n) if(ans[i][++k]!=ans[j][k]) break; //找同构
if(k>n){printf("%d\n",j);break;} //找到同构就输出
}
}
return 0;
}
最新文章
- tornado中self.write() 写list
- CSS超出部分显示省略号…代码
- webpack +vue开发(1)
- php中将url中的参数含有%20进行转换或解码
- mac下Android开发环境搭建
- c# list排序
- HTTP学习笔记7-消息报头
- UVA10765-Doves and bombs(BCC)
- C++链接器工具错误:LNK2001, LNK2019(转载)
- python多线程简单例子
- Linux内核源代码解析——用户发送数据包的起源之sendto
- BZOJ 3402: [Usaco2009 Open]Hide and Seek 捉迷藏(最短路)
- mac下重启apach
- 201521123057《Java程序设计》第14周学习总结
- vue项目中获取cdn域名插件
- Ionic框架搭建简明教程
- Hack You CTF 2014: NotEasyTask
- python cntl使用
- ios中项目
- vue打包完样式冲突
热门文章
- Android Studio如何更新support repository
- xml 写sql语句文件头
- 在iOS项目中,这样才能完美的修改项目名称
- PAT A1135 Is It A Red Black Tree
- teraterm中log中加入时间戳
- FTP、SFTP、SCP的区别
- Linux命令:vmstat命令
- 【PAT甲级】1019 General Palindromic Number (20 分)
- onContextItemSelected 与 onMenuItemSelected 的那些事
- Linux centosVMware LNMP架构介绍、MySQL安装、PHP安装、Nginx介绍