TopCoder Statistics - Problem Statement

Problem Statement

In the country of Byteland, there are N cities connected by N bidirectional roads (that is, the number of roads is the same as the number of cities). The cities are numbered from 0 to N-1. For each i from 0 to N-1, a bidirectional road connects city i and city road[i]. (Note that sometimes a pair of cities can be connected by two distinct roads.) It is possible to travel between any pair of cities using the network of roads.

You are the prime minister of Byteland and you must choose one of the cities to be the capital city. The capital city must have the following property: whenever A and B are two distinct cities, it must be impossible to travel between A and B without visiting the capital.

If there is no valid location for the capital, you must create one. In order to do that, you may modify the road network by doing a sequence of mergers. A merger is an operation that merges two adjacent cities into a single new city. Formally, a merger is performed as follows:

You select two cities X and Y that are directly connected by a road. (They may even be connected by more than one direct road.)
The two cities are merged together to create a new city Z.
All direct roads between X and Y disappear. Each other road that connected X or Y to some other city now connects Z to that other city.

For example, suppose this is the network:

There is no valid location for the capital. However, by merging city 1 and city 2, we can create a valid location:

Now the newly-created city is a valid location for the capital.

You are given the description of the road network in the int[] road. Please find and return the minimum number of mergers necessary to create a valid location for the capital.

Definition

Class:: SuccessfulMerger
Method:: minimumMergers
Parameters:: int[]
Returns:: int
Method signature:: int minimumMergers(int[] road)
(be sure your method is public)

Constraints

N will be between 2 and 50, inclusive.
road will contain N elements.
Each element of road will be between 0 and N-1, inclusive.
For each valid i, road[i] does not equal i.
It will be possible to travel from any city to any other city using the roads.

Examples

{2, 2, 1, 1, 1}

Returns: 1

This test case corresponds to the example from the problem statement. In the given road network there is no valid location for the capital, so at least one merger is needed. The one merger shown above is therefore the optimal solution for this test case.
{3, 4, 5, 4, 5, 3}

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

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

Returns: 2
{31, 19, 0, 15, 30, 32, 15, 24, 0, 20, 40, 1, 22, 21, 39, 28, 0, 23, 15, 5, 19, 22, 6, 32, 8, 38, 35, 30, 4, 28, 32, 18, 18, 9, 22, 41, 20, 18, 6, 25, 41, 34, 4}

Returns: 25
{1, 0}

Returns: 0
{1,0,1}

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

Returns: 1
{4,4,3,1,1}

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

Returns: 3
{10,17,16,6,3,8,8,17,16,17,0,5,0,3,8,18,18,10,1,9}

Returns: 10
{9,3,7,8,12,18,2,11,19,7,13,13,1,19,19,4,10,19,6,3}

Returns: 12
{1,5,27,19,25,14,2,27,11,20,5,25,2,25,17,8,13,20,25,0,5,13,6,3,2,10,9,25}

Returns: 15
{25,6,1,2,18,4,12,13,23,10,6,21,7,4,20,22,20,14,3,16,2,14,1,17,19,23,0,8}

Returns: 19
{3,16,10,6,12,8,1,31,39,26,8,17,40,44,38,18,41,40,23,8,11,26,33,27,9,2,19,31,29,9,5,33,0,3,30,12,21,34,19,12,34,2,1,7,18,26}

Returns: 28
{9,26,15,26,9,35,12,29,11,24,29,9,9,14,20,32,13,21,10,31,29,30,27,10,18,30,0,13,2,16,0,13,18,34,11,18,31}

Returns: 20
{5,13,3,16,10,15,4,12,4,15,7,10,6,9,16,8,11,6}

Returns: 11
{15,14,9,10,11,11,24,21,16,4,8,14,20,22,27,14,0,10,10,4,18,18,15,7,13,23,16,3}

Returns: 17
{31,32,29,17,24,26,8,26,4,1,8,17,5,8,17,17,0,27,20,4,28,11,30,17,7,13,28,37,16,21,3,11,7,10,19,9,24,28}

Returns: 23
{23,25,26,12,10,24,14,0,16,5,7,9,21,4,2,16,26,23,16,9,26,29,14,22,1,16,14,9,21,30,25}

Returns: 17
{5,7,12,8,3,3,2,8,14,13,5,13,9,2,6,13}

Returns: 8
{30,39,25,43,24,41,25,45,36,43,1,16,32,38,24,2,30,0,37,44,12,16,31,16,46,29,35,21,26,36,0,0,0,8,2,40,20,4,9,43,42,12,21,47,12,34,16,16}

Returns: 30
{29,6,42,40,14,33,31,25,19,2,11,7,26,24,15,41,30,38,6,22,46,40,6,41,12,29,11,34,47,31,14,2,3,34,43,4,13,36,35,44,48,5,39,11,39,17,40,10,29}

Returns: 33
{12,13,1,12,11,0,13,14,4,11,17,7,15,18,2,13,9,1,3}

Returns: 12
{5,3,3,4,2,7,2,2}

Returns: 3
{14,45,18,36,7,37,31,21,47,49,44,44,47,15,19,11,43,24,49,43,11,45,15,40,8,11,4,22,40,19,36,18,10,16,24,46,9,48,33,7,9,44,16,17,26,4,0,48,1,11}

Returns: 28
{39,20,3,34,40,33,44,9,29,17,3,43,44,1,47,19,5,13,38,29,36,12,23,41,29,41,47,21,2,2,47,43,37,36,4,34,26,12,2,40,20,8,23,12,42,0,2,15,42,2}

Returns: 28
{49,12,27,26,46,47,9,29,24,23,38,13,17,47,24,33,36,21,31,23,47,7,14,35,31,10,11,30,36,3,4,41,6,44,7,36,22,28,48,7,17,26,32,22,48,29,39,42,24,19}

Returns: 33
{28,6,1,15,10,26,39,9,34,16,11,37,46,39,41,21,40,45,31,24,3,49,15,20,15,1,42,39,7,30,0,12,48,11,49,6,32,38,47,10,15,22,14,21,35,43,16,32,20,41}

Returns: 33
{20,14,37,18,25,45,31,25,28,3,36,15,29,10,38,33,43,23,45,29,30,18,49,45,40,37,27,10,2,40,21,45,26,7,44,40,31,18,44,46,46,6,47,49,12,38,7,28,8,36}

Returns: 29
{27,48,30,39,9,12,32,19,20,36,7,17,47,40,48,14,48,42,45,40,48,47,23,9,17,20,25,24,40,45,39,42,20,24,47,26,29,7,20,44,21,26,25,22,41,13,21,3,42,47}

Returns: 27
{48,23,29,12,14,38,16,23,37,5,14,14,13,2,21,6,29,30,11,13,42,44,8,9,45,13,25,38,27,15,24,45,36,15,17,0,25,38,49,38,38,5,28,17,36,4,33,13,42,44}

Returns: 29
{17,7,12,21,45,36,26,5,31,18,49,22,38,22,9,16,8,4,23,26,28,35,45,1,43,13,40,3,18,10,31,28,39,32,45,36,20,0,25,48,39,44,22,41,38,5,30,31,15,46}

Returns: 35
{15,0,49,42,45,19,41,39,37,8,25,21,19,21,25,16,6,10,24,40,26,47,25,37,28,39,7,8,14,26,46,38,9,32,45,45,38,1,43,21,2,22,34,40,10,27,18,35,17,37}

Returns: 33
{7,12,31,6,36,36,40,20,35,4,1,10,49,37,10,40,48,38,31,16,29,17,25,22,11,7,37,35,25,28,28,21,9,22,26,21,0,2,23,41,46,25,18,12,26,4,13,13,3,20}

Returns: 31
{27,19,45,25,44,20,13,1,6,1,23,2,10,32,16,20,29,7,36,10,8,40,9,15,12,19,47,8,38,37,43,25,28,27,41,16,6,21,44,41,45,46,29,0,49,14,35,40,16,47}

Returns: 32
{45,30,11,37,44,49,2,12,43,45,20,9,39,8,19,9,32,37,36,36,16,48,39,35,4,35,29,6,19,19,5,32,15,10,5,34,5,12,33,29,48,29,49,40,40,23,32,9,38,17}

Returns: 29
{4,46,48,1,1,7,0,8,19,36,32,36,37,42,13,41,28,31,21,49,1,17,5,38,44,31,30,3,33,49,29,41,42,9,25,29,38,40,16,9,27,39,19,13,36,36,42,41,32,28}

Returns: 30
{20,47,4,29,45,12,49,37,39,25,0,27,41,0,34,47,31,35,48,49,36,46,19,3,38,42,42,43,21,34,9,24,33,21,38,2,3,24,30,46,8,38,1,29,48,33,48,15,31,11}

Returns: 32
{41,7,13,0,24,17,47,34,33,41,5,49,1,25,25,9,8,22,38,25,39,12,15,4,17,35,45,16,18,41,22,8,14,48,8,34,2,41,22,17,11,19,10,25,2,22,10,35,11,18}

Returns: 29
{1,2,3,4,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,0}

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

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

Returns: 23
{1,0,1,2,3,4,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}

Returns: 47
{2, 0, 4, 6, 6, 8, 8, 2, 0 }

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

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

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

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

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

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

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

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

Returns: 1
{1, 0 }

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

Returns: 1
{3, 3, 3, 4, 5, 3, 5, 5, 5 }

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

Returns: 1
{1, 2, 1 }

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

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

Returns: 1
{2, 3, 4, 2, 5, 3 }

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

Returns: 1

Statistics

Problem Statement for "SuccessfulMerger"

Problem Statement

Definition

Constraints

Examples