Movie Night
This problem gives us rules about which friends require other friends in order to go out, and asks us the count of combinations of friends.
We see that this is well suited to a graph representation, and representing the links as such gives us a couple intuitions:
- Each node has exactly one outgoing edge
- If there is a cycle or strongly connected component, it MUST be a sink of the graph, otherwise there would be a node with multiple outgoing edges
- Each connected component of the graph consists of a strongly connected comopnent, and "arms" which branch into it
Knowing this, we can start by computing the number of options for a single connected component. We know if anyone is to attend from the this component, it must contain everyone in the cycle/sink, as everyone depends on that cycle, and thus, the entire cycle must be present. For each of the "arms" that dive into this cycle, for an arm of length N, we have N different selections (from none on that arm, to all). We can thus compute the total number of combinations for that connected component as the multiplicity of the lengths of all the arms. If there is an arm of 4, 3, and 2, we end up with 24 different combinations.
Combining multiple connected components is relatively straightforward as well. We have the aforementioned combinations that we computed, as well as an additional combination for each component: representing the situation in which NOBODY from that component is invited. We multiply all those values together, and subtract 1, as we must discount the case that we invite nobody from all the groups.
The only tricks may be:
- Finding the strongly connected components, for which there are standard algorithms
- traversing up the arms to the sources, which can be done by flipping all the edges and BFSing away from the nodes in the SCC