AutomorphicGraph | Topcoder Archive

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.

Definition

Class:: AutomorphicGraph
Method:: count
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int count(int n, int[] a, int[] b)
(be sure your method is public)

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,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.

```
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}
```
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: /\ /__\ /\ /\ /__\/__\

{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

{0,1,2,3,1,2,5,1}

{1,2,3,4,5,6,6,6}

Returns: 1

{0,1,2,3,0,0,7,6,5,1,8,8,2,11,11,3,7,6,18,18,5,15,15,22,22,0,0,23,4,4,25}

{1,2,3,4,4,7,6,5,4,8,9,10,11,12,13,14,21,18,19,20,15,16,17,0,4,23,24,24,25,26,26}

Returns: 128

{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).

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.