BZOJ-4337: BJOI2015 树的同构

[文章目录]

Description

我们把N个点,N-1条边的连通无向图称为树。
若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。
对于两个树T1和T2,如果能够把树T1的所有点重新标号,使得树T1和树T2完全相同,那么这两个树是同构的。也就是说,它们具有相同的形态。
现在,给你M个有根树,请你把它们按同构关系分成若干个等价类。

hash
求树的重心,如果有两个那么新建一个节点连向他们。
之后只要hash的方法交换儿子不改变树的hash值,愿意怎么hash怎么hash

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
#define N 100 
int rt1,rt2,n,m,head[N],to[N<<1],nxt[N<<1],cnt,siz[N];
ll ha[N];
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x,int pre)
{
    siz[x]=1; int tmp=0;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        dfs(to[i],x); tmp=max(tmp,siz[to[i]]);
        siz[x]+=siz[to[i]];
    }
    tmp=max(tmp,n-siz[x]);
    if(tmp<=n/2)
    {
        if(!rt1) rt1=x;
        else rt2=x;
    }
}
ll hash(int x,int pre)
{
    ll re1=0,re2=1,re3=233;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        ll t=hash(to[i],x);
        re1^=t; re2*=t; re3+=t;
    }
    return ((re1*re2)<<15)^re3;
}
int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        memset(head,0,sizeof(int)*(n+10)); cnt=0;
        scanf("%d",&n); int x; rt1=rt2=0;
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&x);
            if(x) add(x,j),add(j,x);
        }
        dfs(1,0);
        if(rt1) add(0,rt1);
        if(rt2) add(0,rt2);
        ha[i]=hash(0,0);
    }
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j) if(ha[j]==ha[i])
        {
            printf("%d\n",j);
            break;
        }
    return 0;
}

发表评论

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