SRM 713, D1, 500-Pointer (DFSCount)

James S. Plank

Sun Jul 2 22:46:57 EDT 2017
Let's attack this problem with an example graph:

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 A. And suppose that we determine the number of DFS's in A, if we start from node 1. Let's call that D(A,1). We can construct a solution that counts all of the DFS' that start with node zero, that is a function of D(A,1) through D(A,6).

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:

D(A,1) + D(A,2)

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:

( D(A,1) + D(A,2) ) * ( D(A,3) + D(A,4) ) * ( D(A,5) + D(A,6) )

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:

3! * ( D(A,1) + D(A,2) ) * ( D(A,3) + D(A,4) ) * ( D(A,5) + D(A,6) )


This now gives us a strategy for solving the problem: Your main program should sum up D(Graph,node) for every node in the original graph.

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 214 elements in each cache -- that's 229,376 elements in the caches -- no problem). That was fast enough!