- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: April, 2017 -
**Competitors who opened the problem**: 194 -
**Competitors who submitted a solution**: 35 -
**Number of correct solutions**: 22 -
**Accuracy (percentage correct vs those who opened)**: 11.3% -
**Accuracy (percentage correct vs those who submitted)**: 62.9% -
**Average Correct Time**: 25 minutes, 48 seconds.

This graph has a lot of nodes and edges, but the ones that we care
about are the ones connected to node 0. If you remove node zero from
the graph, there will be three connected components in the graph,
which I've labeled **A**, **B**, and **C**.

Now, suppose that we are starting with node 0. There are only six
edges out of node zero, so there are only six ways that the DFS can
start. Now, suppose that the DFS starts with node 1. Since it's a
DFS, it will visit all of the nodes in **A**, before it visits any
of the nodes in **B** or **C**. Same thing if it starts with
node 2.

Now, suppose it starts with node 3. That means it will visit all of
the nodes in **B** before it visits any of the nodes in **A**
or **C**. This observation helps us start a solution.

Now, suppose we focus solely on a connected component, like

Let's affix an ordering of how we progress through the components -- suppose we
go through **A** first, then **B**, and then **C**. The number of ways to go
through component **A** may be calculated as:

Similarly, the number of ways to go through component **B** is D(**A**,3) + D(**A**,4), and
the number of ways to go through component **C** is D(**A**,5) + D(**A**,6). Since
these are independent, the number of ways to go through **A**, then **B**, then **C**
is:

If you think about it, it doesn't matter what order you choose to go through the components. Once you choose an order, the number of ways to go through the components in that order is the equation above. Since there are 3! ways to go through the components, the number of ways to go through the graph starting with node zero is:

This now gives us a strategy for solving the problem:

- You are writing a method
`D(component, starting_node).` - To do so, remove
`starting_node`from the graph, and identify the connected components that have edges from`starting_node`. - Suppose that there are
*T*such components. Create a vector`TC`of long long's and resize it to`T`. - For each component
`C`, and each node`n`in`C`with an edge to`starting_node`, calculate`D(C,n)`. Add the result to`T[C]`. - Return the product of all of the elements of
`T`multiplied by*(T!)*.

You have to figure out how to represent a component. What I did was represent it with
a string with *N* characters (assuming there are *N* nodes in the graph).
If a node is in the component, then its character in the string is '1'. Otherwise, it's
zero. Go ahead and write this program. You should be able to test it on examples 0, 1, 2
and 4.

Of course, it blows up exponentially, so you have to memoize on the component and the starting
node. I first did this by turning the component and starting node into a string, and I
had my cache be a map. However, it was too slow. So instead, I used bit arithmetic to represent
a component by a number, and I had a vector of caches -- one for every possible starting node.
(14 possible starting nodes, and 2^{14} elements in each cache -- that's 229,376
elements in the caches -- no problem).
That was fast enough!