BZOJ4337：[BJOI2015]树的同构——题解

时间：2022-08-26 13:08:02

https://www.lydsy.com/JudgeOnline/problem.php?id=4337

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

Q：如何树哈希啊。

A：网上也没有讲解啊，不如看看代码理解一下吧……我就是这么干的。

代码抄自：https://blog.csdn.net/CHNWJD/article/details/78264934当然是没有讲解的。

要注意dfs里的ans一定要有初值！

#include<map>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef unsigned long long ll;

const int N=;

const int B=;

const int p[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt;

}e[N*];

int n[N],m,cnt,head[N];

ll ha[N][N];

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

int dfs(int u,int fa){

    ll num[N],ans=B;int tot=;

    for(int i=head[u];i;i=e[i].nxt){

    int v=e[i].to;

    if(v==fa)continue;

    num[++tot]=dfs(v,u);

    }

    sort(num+,num+tot+);

    for(int i=;i<=tot;i++)ans=ans*B+num[i]*p[i];

    return ans;

}

int main(){

    m=read();

    for(int i=;i<=m;i++){

    n[i]=read();cnt=;

    memset(head,,sizeof(head));

    for(int j=;j<=n[i];j++){

        int v=read();

        if(v)add(j,v),add(v,j);

    }

    for(int j=;j<=n[i];j++)ha[i][j]=dfs(j,);

    sort(ha[i]+,ha[i]+n[i]+);

    bool flag=;

    for(int j=;j<=i&&!flag;j++)

        if(n[i]==n[j])

        for(int k=;k<=n[i];k++){

            if(ha[i][k]!=ha[j][k])break;

            if(k==n[i]){

            printf("%d\n",j);

            flag=;

            }

        }

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

相关文章