Connection Status:
Competition Arena > TrisomorphismEasy

TrisomorphismEasy

SRM 728 · 2018-01-24 · by tourist

SRM 728 · 2018-01-24 · by tourist · Search, Simple Math
Class Name: TrisomorphismEasy
Return Type: int
Method Name: count
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Let S(n) be the set of directed graphs with n vertices labeled from 0 to n-1 such that there is exactly one outgoing edge from each vertex. Self-loops are allowed. Therefore, we have |S(n)| = nn.

Given such a graph, a twirl is an operation that takes three distinct vertices labeled A, B, C and relabels them B, C, A. For example, if you choose the vertices labeled 4, 2, and 77, the following three things will happen simultaneously:

  • The label of the first chosen vertex will change from 4 to 2.
  • The label of the second chosen vertex will change from 2 to 77.
  • The label of the third chosen vertex will change from 77 to 4.

Two graphs are called trisomorphic if we can transform one into the other by performing a sequence of zero or more twirls.

You are given the int[] edgeTo with n elements. This int[] describes a graph G from the set S(n). For each valid i, the graph G contains an edge from vertex i to vertex edgeTo[i].

Return the number of graphs other than G that are trisomorphic to G.

Constraints

  • n will be between 1 and 10, inclusive.
  • edgeTo will contain exactly n elements.
  • Each element of edgeTo will be between 0 and n-1, inclusive.
Examples
0)
{1, 0}
Returns: 0

It's impossible to pick three distinct vertices when n = 2. Every graph is trisomorphic to itself only.

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

The other two graphs trisomophic to the given one are {1, 2, 1} and {1, 0, 0}.

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

Any twirl applied to this graph keeps it unchanged.

3)
{4, 5, 3, 1, 1, 5}
Returns: 179
4)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 9}
Returns: 1814399

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

Coding Area

Language: C++17 · define a public class TrisomorphismEasy with a public method int count(vector<int> edgeTo) · 159 test cases · 2 s / 256 MB per case

Submitting as anonymous