Connection Status:
Competition Arena > Sunnygraphs

Sunnygraphs

SRM 691 · 2016-05-02 · by subscriber

SRM 691 · 2016-05-02 · by subscriber · Graph Theory
Class Name: Sunnygraphs
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 and 1 are in the same connected component. (I.e., there is a path from one of them to the other.) 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 connected. If he chose M = {0}, the resulting graph contained the edges 0-1 and 0-2. The vertices 0 and 1 were connected. If he chose M = {1}, the resulting graph contained the edges 0-1 and 1-2. The vertices 0 and 1 were connected. 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 connected: there is a path 0-1-2. As all four choices of M are good, the correct answer is 4.

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

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

2)
{2,3,0,1}
Returns: 9
3)
{2,2,3,4,3}
Returns: 30
4)
{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: 8787503087616

Watch out for integer overflow.

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

Coding Area

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

Submitting as anonymous