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

喜欢ヅ旅行 2021-10-29 09:30 376阅读 0赞

[传送门][Link 1]

哈希

$dfs$ 枚举所有节点，进入时哈希值加一个左括号，把所有儿子哈希值加入，退出时加一个右括号

因为儿子的顺序可以任意，所以要把儿子哈希值 $sort$ 以后再顺序加入

因为根节点不确定，所以枚举所有节点作为根都算一遍哈希值

比较的时候同样把所有根的哈希值排序后顺序比较，只要有一个不同就不是同构

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<vector>
    using namespace std;
    typedef unsigned long long ull;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=107,base=998244353;
    int n,m;
    ull h[N],ha[N][N];
    vector <int> V[N];
    vector <ull> H[N];
    void dfs(int x,int fa)
    {
        int len=V[x].size(); H[x].clear(); h[x]='(';
        for(int i=0;i<len;i++)
        {
            int &t=V[x][i]; if(t==fa) continue;
            dfs(t,x); H[x].push_back(h[t]);
        }
        sort(H[x].begin(),H[x].end()); len=H[x].size();
        for(int i=0;i<len;i++) h[x]=h[x]*base+H[x][i];
        h[x]=h[x]*base+')';
    }
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            m=read(); int a;
            for(int j=1;j<=m;j++) V[j].clear();
            for(int j=1;j<=m;j++)
            {
                a=read(); if(!a) continue;
                V[a].push_back(j),V[j].push_back(a);
            }
            for(int j=1;j<=m;j++) dfs(j,0),ha[i][j]=h[j];
            sort(ha[i]+1,ha[i]+m+1); int ans=i;
            for(int j=1;j<i;j++)
            {
                bool flag=1;
                for(int k=1;k<=m;k++)
                    if(ha[i][k]!=ha[j][k]) { flag=0; break; }
                if(flag) { ans=j; break; }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LLTYYC/p/11350301.html

[Link 1]: https://www.luogu.org/problem/P5043