Notice that each node has exaclty 1 out edge. The graph would be a tree, with children pointing to the parent, and root pointing to some random child

Also notice that this n node, n edge is composable structure, so potentially there are multiple components

Now assume only 1 component in the graph.

The graph can be broken down into 2 parts

  1. a directed cycle
  
  2. directed trees with roots on that cycle

Proof: Induction on the number of vertices, when we add a new edge, which node should it point to?

  1. if it points to a vertex on the cycle, it has 3 choices, no incoming edge, incoming edge from cycle, incoming edge from tree

  2. If it points to a vertex on the tree, these 3 choices either introduce more branches, or break the old cycle and introduce a new one

Now if the component is just a cycle, then any subset would do => 2^n

If the component is cycle + branch

  1. if branches do not change, any subset from cycle will do =>  2^ size(cycle)
  
  2. if branches change, then any non-empty subset from cycle will do => (2^size(branches) - 1) * (2^size(cycle) -1)

  3. sum it up, we get 2^size(component) + 1 - 2^size(branches)

Now lets consider the multiple component cases

  1. for each component, the argument above still holds, because of the n vertice, n edges structure is composable, except that we have to
exclude empty set case, because each component needs to contribute something to the n node

  2. Therefore, the total # of ways is the product of each indiviual componenets ways - 1 (-1 to exclude empty set case)

  3. therefore, we should DFS the graph to discover the component size and cycle/branch size, and then product result of each component together

Implementation notes

  1. to calculate size of component, need to convert it to undirected graph

  2. to find the length of the cycle, need to use the directed version, and keep a DFSish clock (See Floyd cycle finding).

  3. 1L << shift to calculate power for long