每日一题：Two Graphs（暴力）

题意

给一个小图和一个大图，问大图有多少个子图形状和小图一样。

solution

最多只有8个点，因为每个点标号可能不一样，因此可以全排列枚举所有点的位置，然后判断小图有的边大图是否也有（因为原来边的属性还在），并通过hash进行去重。

Code

#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, res, pre[10], mp1[10][10], mp2[10][10];
map<long long, int> p;
int main() {
  while (~scanf("%d%d%d", &n, &m1, &m2)) {
    memset(mp1, 0, sizeof(mp1));
    memset(mp2, 0, sizeof(mp2));
    p.clear();
    res = 0;
    for (int i = 1; i <= m1; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      mp1[x][y] = mp1[y][x] = 1;
    }
    for (int i = 1; i <= m2; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      mp2[x][y] = mp2[y][x] = i;
    }
    for (int i = 1; i <= n; i++) pre[i] = i;
    do {
      int flag = 1;
      long long now = 0;
      for (int i = 1; i <= n && flag; i++) {
        for (int j = 1; j <= n && flag; j++) {
          if (mp1[i][j] == 1) {
            if (!mp2[pre[i]][pre[j]]) flag = 0;
            now |= 1LL << (mp2[pre[i]][pre[j]]);
          }
        }
      }
      if (flag && p[now] == 0) {
        res++;
        p[now] = 1;
      }
    } while (next_permutation(pre + 1, pre + n + 1));
    printf("%d\n", res);
  }
  return 0;
}