「洛谷 P5043」:树同构【树哈希】

「洛谷 P5043」:树同构【树哈希】P5043【模板】树同构([BJOI2015]树的同构题目描述树是一种很常见的数据结构。我们把NNN个点,N−1N−1N−1条边的连通无向图称为树。若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。对于两个树T1T_1T1​和T2T_2T2​,如果能够把树T1T_1T1​的所有点重新标号,使得树T1T_1T1​和树T2T_2T2​完全相同,那么这两个树是同构的…



P5043 【模板】树同构([BJOI2015]树的同构

题目描述

树是一种很常见的数据结构。

我们把 N N N个点, N − 1 N−1 N1条边的连通无向图称为树。

若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。

对于两个树 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 1N,M50

题意

  • 就是给你 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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注