牛客多校一 D_闵可夫斯基和 多校

链接：https://www.nowcoder.com/acm/contest/139/D
来源：牛客网
 

题目描述

Two undirected simple graphs and where are isomorphic when there exists a bijection on V satisfying  if and only if {x, y} ∈ E2.
Given two graphs and , count the number of graphs satisfying the following condition:
* .
* G1 and G are isomorphic.

输入描述:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains three integers n, m1 and m2 where |E1| = m1 and |E2| = m2.
The i-th of the following m1 lines contains 2 integers ai and bi which denote {ai, bi} ∈ E1.
The i-th of the last m2 lines contains 2 integers ai and bi which denote {ai, bi} ∈ E2.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

3 1 2
1 3
1 2
2 3
4 2 3
1 2
1 3
4 1
4 2
4 3

输出

复制

2
3

备注:

* 1 ≤ n ≤ 8
* 
* 1 ≤ ai, bi ≤ n
* The number of test cases does not exceed 50.

题意：问一个图在另一个图有多少个同构。

题解：

因为每一种排列代表不同的标号。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll MOD = 1E9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m1, m2;
    while(cin >> n >> m1 >> m2) {
        vector<int> a(n);
        for(int i = 0; i < n; ++i) a[i] = i;
        vector< pair<int, int> > edge1(m1), edge2(m2);
        vector<vector<int> > vis(n, vector<int>(n) );
        for(int i = 0; i < m1; ++i) {
            int u, v;
            cin >> u >> v;
            edge1[i] = {--u, --v};
            vis[u][v] = vis[v][u] = 1;
        }
        for(int i = 0; i < m2; ++i) {
            int u, v;
            cin >> u >> v;
            edge2[i] = {u - 1, v - 1};
        }
        set<ll> s;
        do {
            int cnt = 0;
            ll cur = 0;
            for(int i = 0; i < m2; i ++) {
                if(vis[a[edge2[i].first]][a[edge2[i].second]]) {
                    cnt ++;
                    cur = cur * 133 + (i + 53);
                    cur %= MOD;
                }
            }
            if(cnt == m1) s.insert(cur);
        }while(next_permutation(a.begin(), a.end()));
        cout << (int)s.size() << '\n';
    }
    return 0;
}