本文最后更新于 2300 天前,其中的信息可能已经有所发展或是发生改变。
Table of Content
题意
n个点,m1条边的图E1,n个点,m2条边的图E2。求图E2有多少子图跟图E1同构。
题解
由于题目数据范围不大考虑暴力枚举$n!$范围的所有结果。
答案除以自同构数。
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
int n, m1, m2, u[100], v[100], g1[10][10], g2[10][10], a[10];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while (cin >> n >> m1 >> m2) {
memset(g1, 0, sizeof(g1));
memset(g2, 0, sizeof(g2));
for (int i = 1; i <= m1; i++) {
cin >> u[i] >> v[i];
g1[u[i]][v[i]] = g1[v[i]][u[i]] = 1;
}
for (int i = 1; i <= m2; i++) {
int x, y;
cin >> x >> y;
g2[x][y] = g2[y][x] = 1;
}
iota(a + 1,a + 1 + n,1);
int ans = 0, num = 0;
do {
int flag1 = 1, flag2 = 1;
for (int i = 1; i <= m1; i++) {
int x = a[u[i]], y = a[v[i]];
if (!g1[x][y])flag1 = 0;
if (!g2[x][y])flag2 = 0;
}
ans += flag2;
num += flag1;
} while (next_permutation(a + 1, a + n + 1));
cout << ans / num << "\n";
}
}