树同构-树哈希

树同构-树哈希树同构-树哈希题目描述题解对于无根树,由于数据范围较小,可以直接以每个点为根dfs一次,维护其树哈希的值,然后用并查集维护(若数据范围大一些,可以以树的重心跑dfs)代码实现#include<bits/stdc++.h>//树哈希#defineM100009#defineLLunsignedlonglongusingnamespacestd;i…

树同构-树哈希

题目描述

题目描述

题解

对于无根树,由于数据范围较小,可以直接以每个点为根dfs一次,维护其树哈希的值,然后用并查集维护
(若数据范围大一些,可以以树的重心跑dfs)

代码实现

#include<bits/stdc++.h>//树哈希 
#define M 100009
#define LL unsigned long long 
using namespace std;
int v[100],vis[100],cnt,n,m;
int tot,first[M],nxt[M],to[M],fat[M];
map<LL,int>ma;
LL f[M],size[M],p[100];
int getfa(int x){ 
   
	if(fat[x]==x) return x;
	return fat[x]=getfa(fat[x]);
}
void add(int x,int y){ 
   
	nxt[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
}
LL dfs(int u,int fa){ 
   
	size[u]=1,f[u]=1; 
	for(int i=first[u];i;i=nxt[i]){ 
   
		int v=to[i];
		if(v==fa) continue;
		f[u]+=dfs(v,u)*p[size[v]];//较好的树哈希方式,不容易被卡 
		size[u]+=size[v];
	}return f[u];
}
int main(){ 
   
	int x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) fat[i]=i;
	for(int i=2;i<=52;i++){ 
   
		if(!v[i]){ 
   
			p[++cnt]=i;
			v[i]=i;
			vis[i]=1;
		} 
		for(int j=1;j<=cnt;j++){ 
   
			if(v[i]<p[j]||i*p[j]>5) break;
			v[i*p[j]]=p[j];
		}
	}
	for(int i=1;i<=n;i++){ 
   
		scanf("%d",&m),tot=0;
		memset(first,0,sizeof(first));
		for(int j=1;j<=m;j++){ 
   
			scanf("%d",&x);
			if(x)add(j,x),add(x,j);
		}
		for(int j=1;j<=m;j++){ 
   
			LL val=dfs(j,0);
			int w=ma[val];
			int fx=getfa(i),fy=getfa(w);
			if(!w) ma[val]=i;
			else if(fx>fy) fat[fx]=fat[fy],ma[val]=fy;
			else fat[fy]=fx,ma[val]=fx;
		}
	}for(int i=1;i<=n;i++) printf("%d\n",getfa(i));
	return 0; 
} 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35084.html

(0)
编程小号编程小号

相关推荐

发表回复

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