// 105 判断图是否同构.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/14/problem/600
给你两张无向简单图,保证两张图的顶点数和边数相同,请判断这两张图是否同构。
如果同构输出 Yes,否则输出 No。
输入格式
第一行两个整数 n,m,表示图的顶点数和边数,顶点编号从 1到 n。
接下来 m行描述第一张图,每行两个整数 x,y,表示 x号点和 y号点之间有一条边。
再接下来 m行描述第二张图,每行两个整数 x,y,表示 x号点和 y号点之间有一条边。
输出格式
输出一行一个字符串,表示答案。
样例输入
3 2
1 2
2 3
1 3
2 3
样例输出
Yes
数据规模
对于所有数据,保证 1≤n≤8,0≤m≤n(n−1)/2,1≤x,y≤n。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 10;
int g[N][N];
int t[N][N];
int vis[N];
unordered_map<int, int> mm;
int n, m;
bool dfs(int x,int y) {
vis[y] = 1; mm[x] = y;
if (x == n) {
//检查
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] != t[mm[i]][mm[j]]) {
vis[y] = 0; mm[x] = 0;
return false;
}
}
}
return true;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 1) continue;
if (dfs(x + 1, i)) {
return true;
}
}
vis[y] = 0; mm[x] = 0;
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b; g[a][b] = 1; g[b][a] = 1;
}
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b; t[a][b] = 1; t[b][a] = 1;
}
for (int i = 1; i <= n; i++) {
if (dfs(1, i)) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
标签:输出,同构,判断,int,include,号点,105
From: https://www.cnblogs.com/itdef/p/18358409