[51nod1676]无向图同构

　　如果一个无向图重标号后与另一个无向图完全一致(即对于任意两点，他们之间的边在两个图中都存在或都不存在)，则称两个无向图同构。
　　给定两个n个点m条边的无向图，判定两个无向图是否同构。不超过20组数据，n<=200,m<=4000

　　只要hash值相等就好了。。权值排序那部分不用在算每个点的时候都重新排序。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define ll long long

 #define ui unsigned int

 #define ull unsigned long long

 const int maxn=,inf=;

 struct zs1{int too,pre;}e1[],e2[];int tot1,last1[maxn],tot2,last2[maxn];

 struct zs{int id;ull v;}a1[][maxn],a2[][maxn];

 int p1[maxn],p2[maxn];

 int i,j,k,n,m;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while((rx<''||rx>'')&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;

 }

 inline void ins1(int a,int b){

     e1[++tot1].too=b,e1[tot1].pre=last1[a],last1[a]=tot1;

     e1[++tot1].too=a,e1[tot1].pre=last1[b],last1[b]=tot1;

 }

 inline void ins2(int a,int b){

     e2[++tot2].too=b,e2[tot2].pre=last2[a],last2[a]=tot2;

     e2[++tot2].too=a,e2[tot2].pre=last2[b],last2[b]=tot2;

 }

 bool operator <(zs a,zs b){return a.v<b.v;}

 int main(){

     register int i,j;ull k;

     for(int T=read();T;T--){

         tot1=tot2=,memset(last1+,,n<<);memset(last2+,,n<<);

         n=read(),m=read();

         for(i=;i<=m;i++)ins1(read(),read());

         for(i=;i<=m;i++)ins2(read(),read());

         for(i=;i<=n;i++)a1[][i]=a2[][i]=(zs){i,1ull},ins1(i,i),ins2(i,i),a1[][i].id=a2[][i].id=p1[i]=p2[i]=i;

         bool now=,pre=;int p;

         for(p=n;p;p--,now^=,pre^=){//printf("now,pre:%d %d\n",now,pre);

             for(i=;i<=n;i++)a1[now][i].v=a2[now][i].v=;//,printf("    %llu %llu\n",a1[pre][i].v,a2[pre][i].v);

             for(i=;i<=n;i++)p1[a1[now][i].id]=p2[a2[now][i].id]=i;

             for(i=;i<=n;i++){

                 for(j=last1[a1[pre][i].id],k=a1[pre][i].v/*,printf("   %llu\n",k)*/;j;j=e1[j].pre)

                     (a1[now][p1[e1[j].too]].v*=2333ull)+=k;

                 for(j=last2[a2[pre][i].id],k=a2[pre][i].v;j;j=e2[j].pre)

                     (a2[now][p2[e2[j].too]].v*=2333ull)+=k;

             }

             std::sort(a1[now]+,a1[now]++n),

             std::sort(a2[now]+,a2[now]++n);

             for(i=;i<=n&&a1[now][i].v==a2[now][i].v;i++);//printf("        %llu %llu\n",a1[now][i].v,a2[now][i].v);

             if(i<=n)break;

         }puts(!p?"YES":"NO");

     }

 }