Connection Status:
Competition Arena > AutomorphicGraph

AutomorphicGraph

SRM 703 · 2016-12-04 · by cgy4ever

SRM 703 · 2016-12-04 · by cgy4ever · Graph Theory, Math
Class Name: AutomorphicGraph
Return Type: int
Method Name: count
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

You have an undirected graph G with n vertices and m edges. The vertices are numbered 0 through n-1. You are given the int n. You are also given the int[]s a and b, each with m elements. For each valid i, the graph G contains the edge between a[i] and b[i].

The graph G is guaranteed to have the following properties:
  • G is simple: there are no self-loops and no multiple edges.
  • G is connected: each vertex is reachable from each other vertex by following a sequence of edges.
  • The number of edges is between n+1 and n+5, inclusive.
An automorphism of a graph is an isomorphism between two copies of the graph. Formally, an automorphism of a graph is a permutation p of {0, 1, ..., n-1} with the following property: For each i and j, vertices i and j are connected by an edge if and only if vertices p[i] and p[j] are connected by an edge.

Compute the number of automorphisms of the given graph, and return that value modulo 10^9 + 7.

Constraints

  • n will be between 4 and 100, inclusive.
  • m will be between n+1 and n+5, inclusive.
  • a and b will contain exactly m elements.
  • All elements in a and b will be between 0 and n-1, inclusive.
  • The graph G will be simple and connected.
Examples
0)
5
{0,0,0,0,1,1,1,2,2,3}
{1,2,3,4,2,3,4,3,4,4}
Returns: 120

The graph is G5, so all 5! = 120 permutations are good.

1)
4
{0,0,0,2,2}
{1,2,3,1,3}
Returns: 4

This time we have 4 permutations: {0, 1, 2, 3} {0, 3, 2, 1} {2, 1, 0, 3} {2, 3, 0, 1}

2)
6
{0,0,1,1,1,3,2,2,4}
{1,2,2,3,4,4,4,5,5}
Returns: 6

The graph looks like this: /\ /__\ /\ /\ /__\/__\

3)
12
{0,1,2,3,4,5,6,7,8,0,3,6,1,4,7}
{1,2,3,4,5,6,7,8,0,3,6,0,9,10,11}
Returns: 3
4)
7
{0,1,2,3,1,2,5,1}
{1,2,3,4,5,6,6,6}
Returns: 1
6)
67
{0,1,2,3,1,2,5,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,66}
{1,2,3,4,5,6,6,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34}
Returns: 73741817

The answer is (2^30) % (10^9+7).

Submissions are judged against all 131 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AutomorphicGraph with a public method int count(int n, vector<int> a, vector<int> b) · 131 test cases · 2 s / 256 MB per case

Submitting as anonymous