Connection Status:
Competition Arena > Sunnygraphs2

Sunnygraphs2

SRM 691 · 2016-05-02 · by subscriber

SRM 691 · 2016-05-02 · by subscriber · Graph Theory
Class Name: Sunnygraphs2
Return Type: long
Method Name: count
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Hero has just constructed a very specific graph. He started with n isolated vertices, labeled 0 through n-1. For each vertex i Hero then chose a vertex a[i] (other than i) and he added an edge that connected i and a[i]. This way he created a graph with n vertices and n edges. Note that if a[x]=y and a[y]=x, the vertices x and y were connected by two different edges. Hero now wants to perform the following procedure:
  1. Add a new isolated vertex number n.
  2. Choose a subset M of the original vertices.
  3. For each x in M, erase an edge between vertices x and a[x].
  4. For each x in M, add a new edge between vertices x and n.
Hero's goal is to create a final graph in which the vertices 0 through n-1 are all in the same connected component. (I.e., there must be a way to reach any of these vertices from any other of them by following one or more consecutive edges, possibly visiting vertex n along the way.) Note that Hero does not care whether vertex n is in the same component as the other vertices: both possibilities are fine. In step 2 of the above procedure Hero has 2^n possible subsets to choose from. A choice of M is good if it produces a graph with the desired property. Count how many of the 2^n possibilities are good choices. Return that count as a long.

Constraints

  • a will contain n elements.
  • n will be between 2 and 50, inclusive.
  • Each element in a will be between 0 and n - 1, inclusive.
  • For each i between 0 and n - 1 holds a[i] != i.
Examples
0)
{1,0}
Returns: 4

The original graph contained the vertices 0 and 1. This pair of vertices was connected by two edges. Next, Hero added a new vertex 2. Then he had to choose one of four possible subsets M: If he chose M = {}, the resulting graph contained the edges 0-1 and 0-1. The vertices 0 and 1 were in the same component. If he chose M = {0}, the resulting graph contained the edges 0-1 and 0-2. The vertices 0 and 1 were in the same component. If he chose M = {1}, the resulting graph contained the edges 0-1 and 1-2. The vertices 0 and 1 were in the same component. Finally, if he chose M = {0, 1}, the resulting graph contained the edges 0-2 and 1-2. And again, the vertices 0 and 1 were in the same component. (In the resulting graph we can still go from vertex 0 to vertex 1, even though we have to go via vertex 2.) As all four choices of M are good, the correct answer is 4.

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

Here, M = {2} is not a good choice. This choice produces a graph with edges 0-1, 0-1, and 2-3. In this graph vertex 2 is not in the same component as vertices 0 and 1. The other seven possible choices of M are all good.

2)
{2,3,0,1}
Returns: 9
3)
{2,3,0,1,0}
Returns: 18
4)
{2,3,0,1,0,4,5,2,3}
Returns: 288
5)
{29,34,40,17,16,12,0,40,20,35,5,13,27,7,29,13,14,39,42,9,30,38,27,40,34,33,42,20,29,42,12,29,30,21,4,5,7,25,24,17,39,32,9}
Returns: 6184752906240

"Watch out for integer overflow."

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

Coding Area

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

Submitting as anonymous