[51nod1676]无向图同构

时间：2021-09-06 22:20:11

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

题解：初始时设每个点为点权为1，之后进行n次迭代，每次迭代每个点的值更替为与其相邻的点和他本身上一次迭代后的权值排序后计算出的hash值。

　　只要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");

     }

 }

相关文章