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

  • 2018-07-24
  • 34
  • 0

题目:

Two undirected simple graphs img and img where img are isomorphic when there exists a bijection img on V satisfying img if and only if {x, y} ∈ E2.
Given two graphs img and img, count the number of graphs img satisfying the following condition:
* img.
* 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代码:

评论

还没有任何评论,你来说两句吧