例题:
结绳游戏
给出两张 n 个结点 m 条边的图,问在不考虑结点编号的情况下两张图是否相同,即问两张图是否同构
#include<iostream>
#include<algorithm>
using namespace std;
int p[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
int n, m;
int g[10][10], h[10][10];
int main() {
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++) cin >> x >> y, g[x][y] = g[y][x] = true;
for(int i = 1, x, y; i <= m; i++) cin >> x >> y, h[x][y] = h[y][x] = true;
do {
int f = 1;
for(int i = 1; i <= n && f; i++)
for(int j = 1; j <= n && f; j++)
if(g[i][j] ^ h[p[i]][p[j]]) f = 0;
//当g[i][j]与h[p[i]][p[j]]都不相连或都相连时,f=1,只有当一个相连,另一个不相连时f=1
if(f) {
puts("Yes");
return 0;
}
} while(next_permutation(p + 1, p + n + 1));//存储在 #include<algorithm>中,遍历全排列
puts("No");
return 0;
}