树同构-树哈希
题目描述
题解
对于无根树,由于数据范围较小,可以直接以每个点为根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