bzoj 4337 BJOI2015 树的同构

bzoj 4337 BJOI2015 树的同构

Description

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

Solution

乍一看这数据这么小，直接乱Hash就好了。 我的Hash是dfs每个子节点的val排序一遍然后times {base}^i。

Code

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;

#define re register 
#define mod 19260817
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd) fread(Rd,1,S,stdin),A==B)?EOF:*A  )
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x '0');
            else write(x/10),pc(x '0');
        }
        #undef gc
        #undef pc
}I;

class Solve{
    private:
        int m,n,fir[55],nxt[55*2],son[55*2],tot,ans[55][55],put[55];
    public:
        inline void add(int x,int y){
              tot;
            nxt[tot]=fir[x];
            fir[x]=tot;
            son[tot]=y;
        }
        inline int DFS(int x,int fa){
            int sum=1;
            vector<int> v;v.clear();
            for(int to,i=fir[x];i;i=nxt[i]){
                to=son[i];
                if(to==fa) continue ;
                int tmp=DFS(to,x);
                v.push_back(tmp);
            }
            sort(v.begin(),v.end());
            int base=233;
            for(vector<int>::iterator i=v.begin();i!=v.end();i  ){
                sum =(*i)*base%mod;sum%=mod;
                base*=233;base%=mod;
            }
            return sum;
        }
        inline void init(){
            m=I.read();
            for(int i=1;i<=m;i  ){
                n=I.read();
                memset(fir,0,sizeof(fir));tot=0;
                for(int x,j=1;j<=n;j  ){
                    x=I.read();
                    if(x==0) continue ;
                    add(x,j);add(j,x);
                }
                ans[i][0]=n;
                for(int j=1;j<=n;j  ){
                    ans[i][j]=DFS(j,0);
                }
                sort(ans[i] 1,ans[i] n 1);
                put[i]=i;
                for(int j=1;j<i;j  ){
                    if(ans[i][0]==ans[j][0]){
                        int ff=0;
                        for(int k=1;k<=n;k  ){
                            if(ans[j][k]==ans[i][k]) ;
                            else{
                                ff=1;
                                break ;
                            }
                        }
                        if(ff==0){
                            put[i]=put[j];
                            break ;
                        }
                    }
                }
            }
            for(int i=1;i<=m;i  ) cout<<put[i]<<endl;
        }
}S;
signed main(){S.init();}

dfs hash ode

0 人点赞