大家好，又见面了，我是你们的朋友全栈君。
题目
Problem Description
如果一个无向图重标号后与另一个无向图完全一致(即对于任意两点，他们之间的边在两个图中都存在或都不存在)，则称两个无向图同构。
给定两个n个点m条边的无向图，判定两个无向图是否同构。
Input
第一行一个数T，表示有T组数据(T<=20)
对于每一组数据：
第一行两个数n,m，表示要判定的两个无向图都是n个点m条边(n<=200,m<=4000)
接下来m行，每行两个数x,y，表示在第一个图中存在一条边连接点x和点y(1<=x,y<=n)
接下来m行，每行两个数x,y，表示在第二个图中存在一条边连接点x和点y(1<=x,y<=n)Output
对于每一组数据，如果两个无向图同构则输出”YES”，否则输出”NO”
Sample Input
4
5 6
1 2
1 3
1 5
4 1
2 3
5 4
3 1
5 4
3 4
2 3
3 5
1 25 6
1 2
1 3
1 5
4 1
2 3
5 4
3 1
5 4
3 4
2 3
3 5
1 43 2
1 2
2 3
2 1
1 34 3
1 2
2 3
3 4
1 2
1 3
1 4Sample Output
YES
NO
YES
NO
分析
- 看两个图是否同构，可以想到用哈希值来确定一个图。
- 那么对于一个图，它的哈希值就应该只和它的结构有关，和点的编号无关，于是可以有下面这种哈希规则
- 对于每个点，它的哈希值是它的权值与“和它相邻的点”的权值的和（当然可以再乘一些数再模一下）。
- 起初全部点的权值都为 1，然后进行多次改变操作，每次中先把点按上一次的权值排个序，再按上面的规则修改哈希值即可。
- 由于排了序，那么此图的哈希值就只会和它的结构有关了。
- 进行多次改变后，若两个图中的点，权值情况相同，那么我们就可以看成它们同构了。（当然运气不好可能可以被卡，那就多变换几次，哈希操作也弄复杂一点吧）
程序
#include <cstdio>
#include <algorithm>
#define For(G,x) for(int h=G.head[x],o=G.V[h]; h; o=G.V[h=G.to[h]])
#define N 205
#define M 4005
using namespace std;
struct Tu{
int head[N],to[M*2],V[M*2],num;
void Add(int x,int y){to[++num]=head[x],head[x]=num,V[num]=y;}
}A,B;
struct zzk{
int id,v;} a[2][N],b[2][N];
int n,m,cnt,k,F=1,f1[2][N],f2[2][N];
bool cmp(zzk x,zzk y){
return x.v<y.v;}
void Hash(){
sort(a[cnt]+1,a[cnt]+n+1,cmp);
sort(b[cnt]+1,b[cnt]+n+1,cmp);
for (int i=1,u=a[cnt][i].id; i<=n; i++,u=a[cnt][i].id){
k=f1[cnt][u]*18; //随意弄个规则修改 Hash 值
For(A,u) k+=f1[cnt][o]*666233;
a[cnt^1][i].id=u;
f1[cnt^1][u]=a[cnt^1][i].v=k;
}
for (int i=1,u=b[cnt][i].id; i<=n; i++,u=b[cnt][i].id){
k=f2[cnt][u]*18; //用同一个规则修改 Hash 值
For(B,u) k+=f2[cnt][o]*666233;
b[cnt^1][i].id=u;
f2[cnt^1][u]=b[cnt^1][i].v=k;
}
cnt^=1;
}
int main(){
for (int T=(scanf("%d",&T),T),uu,vv; T--; F=1){
A.num=B.num=0;
for (int i=1; i<=n; i++) A.head[i]=B.head[i]=0;
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++) scanf("%d%d",&uu,&vv),A.Add(uu,vv),A.Add(vv,uu);
for (int i=1; i<=m; i++) scanf("%d%d",&uu,&vv),B.Add(uu,vv),B.Add(vv,uu);
for (int i=1; i<=n; i++){
a[0][i].id=a[1][i].id=b[0][i].id=b[1][i].id=i;
f1[cnt][i]=a[cnt][i].v=f2[cnt][i]=b[cnt][i].v=1;
}
for (int i=1; i<=n; i++) Hash(); //多次变换
sort(a[cnt]+1,a[cnt]+n+1,cmp);
sort(b[cnt]+1,b[cnt]+n+1,cmp);
for (int i=1; i<=n; i++)
if (a[cnt][i].v!=b[cnt][i].v) {F=0; break;}
puts(F?"YES":"NO");
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/126321.html原文链接：https://javaforall.net
