牛客网暑期ACM多校训练营（第一场） D Two Graphs

Description:

Two undirected simple graphs $G_1 = \langle V, E_1 \rangle$ and $G_2 = \langle V, E_2 \rangle$ where $V = \{1, 2, \dots, n\}$ are isomorphic when there exists a bijection $\phi$ on V satisfying $\{\phi(x), \phi(y)\} \in E_1$ if and only if {x, y} ∈ E2.
Given two graphs $G_1 = \langle V, E_1 \rangle$ and $G_2 = \langle V, E_2 \rangle$ , count the number of graphs $G = \langle V, E \rangle$ satisfying the following condition:

$E \subseteq E_2$ .
G1 and G are isomorphic.

Input:

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.

Output:

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

Sample Input:

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

Sample Output:

2
3

题目链接

暴力枚举G1的每一种映射（双射），通过图G1和G2的邻接矩阵判断这个映射是否是它们的同构图，分别统计，最后用除法去重。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 3e2+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int n, m1, m2;
int cnt1, cnt2;
bool adj1[maxn][maxn];
bool adj2[maxn][maxn];
int _map[maxn];

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	while (~scanf("%d%d%d", &n, &m1, &m2)) {
		mem(adj1, 0);
		mem(adj2, 0);
		cnt1 = 0, cnt2 = 0;
		vector<PII> edge;
		// 读入G1的每一条边并构建G1邻接矩阵
		for (int i = 0, a, b; i < m1; ++i) {
			read(a); read(b);
			edge.pb(mp(a, b));
			adj1[a][b] = adj1[b][a] = 1;
		}
		// 构建G2邻接矩阵
		for (int i = 0, a, b; i < m2; ++i) {
			read(a); read(b);
			adj2[a][b] = adj2[b][a] = 1;
		}
		// 初始化映射
		for (int i = 1; i <= n; ++i) {
			_map[i] = i;
		}
		// 全排列映射
		do {
			// 标记此种映射是否是G1自同构或者G2同构
			bool flag1 = 1, flag2 = 1;
			for (auto i : edge) {
				if (!adj1[_map[i.first]][_map[i.second]]) {
					flag1 = 0;
				}
				if (!adj2[_map[i.first]][_map[i.second]]) {
					flag2 = 0; 
				}
			}
			// 若此种映射为G1自同构cnt1++
			if (flag1) {
				++cnt1;
			}
			// 若此种映射为G2同构cnt2++
			if (flag2) {
				++cnt2;
			}
		} while(next_permutation(_map + 1, _map + n + 1));
		printf("%d\n", cnt2 / cnt1);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}