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.
Definition
- Class:
- TrisomorphismEasy
- Method:
- count
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int count(int[] edgeTo)
- (be sure your method is public)
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
{1, 0}Returns: 0
It's impossible to pick three distinct vertices when n = 2. Every graph is trisomorphic to itself only.{2, 2, 0}Returns: 2
The other two graphs trisomophic to the given one are {1, 2, 1} and {1, 0, 0}.{0, 1, 2, 3}Returns: 0
Any twirl applied to this graph keeps it unchanged.{4, 5, 3, 1, 1, 5}Returns: 179
{1, 2, 3, 4, 5, 6, 7, 8, 9, 9}Returns: 1814399