2018牛客多校01 D Two Graphs

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/139/D

求G1的同构图，是G2的子图。

暴力枚举全排列，对于每一个排列，看看G2中是否每一条边都存在，然后再看看是否每一条边都在G1中存在（这里存在的话必然会重复计数），然后用上一个计数结果除以下一个即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 11;
int n;
int m1, m2;
int id[maxn];
int b[maxn][maxn], c[maxn][maxn];
vector<int> a[maxn];
 
signed main() {
  // freopen("in", "r", stdin);
  int x, y;
  while(~scanf("%d%d%d",&n,&m1,&m2)) {
    for(int i = 1; i <= n; i++) {
      a[i].clear();
    }
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for(int i = 1; i <= m1; i++) {
      scanf("%d%d",&x,&y);
      a[x].push_back(y);
      a[y].push_back(x);
      c[x][y] = c[y][x] = 1;
    }
    for(int i = 1; i <= m2; i++) {
      scanf("%d%d",&x,&y);
      b[x][y] = b[y][x] = 1;
    }
    for(int i = 1; i <= n; i++) {
      id[i] = i;
    }
    if(m1 > m2) {
      printf("0\n");
      continue;
    }
    int ret = 0, tot = 0;
  do {
    int flag = 1;
    for(x = 1; x <= n; x++) {
      for(int j = 0; j < a[x].size(); j++) {
        y = a[x][j];
        if(!b[id[x]][id[y]]) {
        flag = 0;
        break;
        }
      }
    }
    if(flag) ret++;
    flag = 1;
    for(x = 1; x <= n; x++) {
      for(int j = 0; j < a[x].size(); j++) {
        y = a[x][j];
        if(!c[id[x]][id[y]]) {
          flag = 0;
          break;
        }
      }
    }
    if(flag) tot++;
  }while(next_permutation(id+1, id+n+1));
  printf("%d\n", ret / tot);
  }
  return 0;
}