【题目描述】
Tom和Jerry各有一个玩具，每个玩具都是由M根绳子连接到N个球上制成的。
在Tom的玩具中，球的编号为1,…,N，第i条绳子将球Ai和Bi连接起来。
类似地，在Jerry的玩具中，球编号为1,…,N，第i条绳子将连接到球Ci和球Di。
在每个玩具中，没有球把一条绳子的两端都系在自己身上，也没有两个球被两条或更多
不同的绳子系在一起。
Mike想知道这两个玩具的形状是否相同。
这里，当序列P满足以下条件时，它们被称为具有相同的形状。
• P是(1,…,N)的一个排列。
• 对于1和N（包括1和N）之间的每一对整数i和j，以下公式成立：Tom玩具中的球
i和球j用绳子系着，当且仅当Jerry玩具中的球Pi和球Pj用绳子系着。
如果两个玩具形状相同，请输出“Yes”；否则，请输出“No”。
【输入格式】
第一行有两个整数N和M（1≤N≤8；0≤M≤
∗(−1)
2
）。
接下来有M行，每行两个整数Ai和Bi ，表示Tom玩具上第i根绳子连接的两个球。
接下来还有M行，每行两个整数Ci和Di ，表示Jerry玩具上第i根绳子连接的两个球。
【输出格式】
如果Tom和Jerry的玩具形状相同，请输出“Yes”；否则，请输出“No”。
模拟题目信息，dfs枚举出全排列方案，满足要求则两图同构。
通过邻接矩阵判定：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=9,M=2e5+10;
4 bool a[9][9],b[9][9];//邻接矩阵
5 bool st[9];//全排列的标记
6 int c[9];//记录全排列
7 int n,m,x,y;
8
9 bool dfs(int u){
10 if(u==n+1){
11 for(int i=1;i<=n;i++)
12 for(int j=1;j<=n;j++)
13 if(a[i][j]!=b[c[i]][c[j]]) return false;
14 return true;
15 }
16 for(int i=1;i<=n;i++){
17 if(!st[i]){//i未被选，可以选择i
18 st[i]=true;
19 c[u]=i;
20 if(dfs(u+1)) return true;
21 st[i]=false;//回溯取消标记
22 }
23 }
24 return false;//找不到一种合法全排列
25 }
26
27 int main(){
28 scanf("%d%d",&n,&m);
29 for(int i=1;i<=m;i++){
30 int x,y;
31 scanf("%d%d",&x,&y);
32 a[x][y]=a[y][x]=true;//有连边
33 }
34 for(int i=1;i<=m;i++){
35 int x,y;
36 scanf("%d%d",&x,&y);
37 b[x][y]=b[y][x]=1;
38 }
39 if(dfs(1)) puts("Yes\n");
40 else puts("No\n");
41 return 0;
42 }
