Connection Status:
Competition Arena > CactusAutomorphisms

CactusAutomorphisms

SRM 419 · 2008-09-24 · by andrewzta

SRM 419 · 2008-09-24 · by andrewzta · Graph Theory, Math
Class Name: CactusAutomorphisms
Return Type: int
Method Name: count
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

A vertex cactus is a connected graph such that each vertex belongs to at most one simple cycle. A simple cycle is a cycle that doesn't pass through any vertex more than once. For example, the graph in the picture below is a vertex cactus:

Given a graph G with vertices numbered from 1 to n, its automorphism is a permutation p[1], p[2], ..., p[n] such that there is an edge i-j in G if and only if there is an edge p[i]-p[j].

You are given an int n - the number of vertices in a vertex cactus. The vertices are numbered 1 to n. The edges of the graph are given to you in the String[] edges. Concatenate the elements of edges to get a comma-separated list of integer pairs. The integers in each pair are separated by a space. The pair "i j" (quotes for clarity) means that there is an edge between vertices i and j in the given graph. Return the number of automorphisms that exist for the given vertex cactus, modulo 10^9+3.

Constraints

  • n will be between 1 and 200, inclusive.
  • edges will contain between 0 and 50 elements, inclusive.
  • Each element of edges will contain between 1 and 50 characters, inclusive.
  • When concatenated edges will contain a comma separated list of pairs of integers.
  • Each integer pair will contain two distinct integers between 1 and n, inclusive, separated by a space.
  • The given graph will be a vertex cactus - it will be connected and each vertex will belong to at most one simple cycle.
  • Every pair of vertices in the graph will be connected by at most one edge.
Examples
0)
4
{"1 2,1 3,1 4"}
Returns: 6

We can arbitrarily permute vertices 2, 3 and 4.

1)
4
{"1 2,2 3,3 4,4 1"}
Returns: 8

The permutation can either perform a circular shift of the vertices along the cycle, or flip the cycle, or both.

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

The permutation can swap triangles. Also, in each triangle, the permutation can swap the two vertices that are not incident to another triangle.

3)
18
{"1 2,2 3,3 4,2 4,1 5,1 10,5 10,5 6,6 7",
 ",7 8,7 16,7 17,7 9,6 9,10 18,18 ",
 "12,12 11,11 18,12 13,12 14,12 15"}
Returns: 144

This is the graph in the picture in the problem statement.

4)
1
{}
Returns: 1

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

Coding Area

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

Submitting as anonymous