P5043 【模板】树同构([BJOI2015]树的同构
P5043 【模板】树同构([BJOI2015]树的同构
题目描述
树是一种很常见的数据结构。
我们把 N N N个点, N − 1 N−1 N−1条边的连通无向图称为树。
若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。
对于两个树 T 1 T_1 T1和 T 2 T_2 T2,如果能够把树 T 1 T_1 T1的所有点重新标号,使得树 T 1 T_1 T1和树 T 2 T_2 T2完全相同,那么这两个树是同构的。也就是说,它们具有相同的形态。
现在,给你 M M M个有根树,请你把它们按同构关系分成若干个等价类。
输入格式
第一行,一个整数 M M M。
接下来 M M M行,每行包含若干个整数,表示一个树。第一个整数 N N N表示点数。接下来 N N N个整数,依次表示编号为 1 1 1到 N N N的每个点的父亲结点的编号。根节点父亲结点编号为 0 0 0。
输出格式
输出 M M M行,每行一个整数,表示与每个树同构的树的最小编号。
输入输出样例
输入 #1
4
4 0 1 1 2
4 2 0 2 3
4 0 1 1 1
4 0 1 2 3
输出 #1
1
1
3
1
说明/提示
编号为 1 , 2 , 4 1, 2, 4 1,2,4 的树是同构的。编号为 3 3 3 的树只与它自身同构。
100 % 100\% 100% 的数据中, 1 ≤ N , M ≤ 50 1\leq N,M\leq50 1≤N,M≤50
题意
- 就是给你 m m m颗有根树,问与每一棵树同构的最早输入的那棵树是哪一个
题解
- 树 H a s h Hash Hash模板题
- 也就是给每一个节点赋一个值,然后先求出以儿子为根的子树的 h a s h hash hash,然后用进制 h a s h hash hash依次把当前节点和所有儿子结合到一起,显然如果两棵树是同构的,但是如果 h a s h hash hash时的顺序不一样, h a s h hash hash的结果也是不一样的,所以考虑给所有的儿子的 h a s h hash hash值排序再从小到大做 h a s h hash hash
- 判断两棵树是否同构不能只是 n 2 n^2 n2枚举两颗树的根结点并判断以他们两个为根的树 h a s h hash hash是否相同,相同就是同构的。正确的姿势应该是给每一棵树以每一个节点为根的树 h a s h hash hash排序,然后比较两棵树对应的排序后的数组是否完全一致,如果是,则同构
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
const int base=23333;
const long long mod=998244353;
int ans[maxn][maxn],fa[maxn],n,m,a[maxn];
vector<int> vec[maxn];
long long dfs(int cur,int fa) {
vector<long long> sta;long long ans=base;
for(int i=0;i<vec[cur].size();i++) if(vec[cur][i]!=fa) sta.push_back(dfs(vec[cur][i],cur));
sort(sta.begin(),sta.end());
for(auto i:sta) ans=ans*base+i;
return ans;
}
int main() {
scanf("%d",&m);
for(int i=1;i<=m;i++) {
scanf("%d",&a[i]); //n of each tree
n=a[i];
for(int j=1;j<=n;j++) {
scanf("%d",&fa[j]);
if(!fa[j]) continue;
vec[j].push_back(fa[j]);
vec[fa[j]].push_back(j);
}
for(int j=1;j<=n;j++) ans[i][j]=dfs(j,0);
sort(ans[i],ans[i]+n+1);
int same=i;
for(int j=1;j<n;j++) {
bool ok=true;
if(a[i]!=a[j]) continue;
for(int k=1;k<=n;k++) if(ans[j][k]!=ans[i][k]) {
ok=false;break;}
if(ok) {
same=j;break;}
}
printf("%d\n",same);
for(int i=1;i<=n;i++) vec[i].clear();
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35025.html