1
$\begingroup$

Suppose there are n nodes.
These nodes are connected by m unique directed edges. Sets of these edges may form cycles.
Each node has an associated quantity.
r of these nodes are selected as root nodes.

A node a can be said to reach node b if

  • a is b or
  • there exists a directed path from a to b.

The goal: For each root node, find the sum of the quantities of all nodes which it can reach and no other root can reach.

This includes the root itself. For example, if root 2 can reach root 1, then root 1's associated quantity will be counted to neither root 1 nor root 2's sum. On the other hand, if no root other than root 1 can reach root 1, then root 1's associated quantity will be counted toward root 1's sum.

I'm trying to puzzle out how to do this with the minimum number of calculations, but I think I need to brush up on my graph theory. This problem is quite a lot easier on a tree, but I've found dealing with cycles makes things much more complicated. I'm having a tough time finding a solution which doesn't incessantly re-traverse the graph.

$\endgroup$
0
$\begingroup$

This can be solved in linear time:

Initially, treat all vertices as unmarked.

In phase 1, do a DFS from the first root $r_1$, and mark all reachable vertices as reachable from $r_1$.

Next, in phase 2, do a DFS from the second root $r_2$. Mark all reachable vertices as reachable from $r_2$, except that if you ever encounter a vertex that was previously marked as reachable by $r_1$, delete that vertex and all vertices reachable from it and don't continue the DFS from that vertex.

Repeat, with one phase per root. At each stage, if you ever encounter a vertex that was previously marked as reachable from some other root, then you delete that vertex from the graph and all vertices reachable from it and don't continue the traversal from there.

At the end, do a linear scan over all vertices that have not yet been deleted. Each vertex will either be unmarked or will be marked as reachable from a single root. You can easily count the number that are reachable from each root (and no other) during this linear scan.

Correctness: any vertex that is reachable from two or more vertices are deleted. So, we only consider vertices that are reachable from one root and not any other.

Running time: each vertex is visited during at most two phases: once when it is initially marked as reachable, and possibly a second phase where it is reachable from some other root (but there won't be a third or later phase, because if it is visited in two different phases, it will be deleted). Thus, the total running time for all the phases is at most twice the cost of a DFS, i.e., $O(|V|+|E|)$. The running time for the final scan is $O(|V|)$. Consequently, the total running time is $O(|V|+|E|)$.

$\endgroup$
0
$\begingroup$

A rough sketch, you can fill in the details:

Using Strongly Connected Components (SCCs), you can reduce the graph to a DAG. If you run topological sort on this DAG, all incoming edges to a node will be processed before any outgoing edges. Then just store at each node which root has reached it, or if none/more than one roots have reached it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.