如何快速求解单入口节点下单个节点的支配集？

Great question! Since you're working with a tree (not a general directed graph), you can completely skip Tarjan's algorithm—there's a far simpler, more efficient approach tailored exactly to your single-node use case.

Why Trees Make This Easy #

In a tree, there's exactly one unique path from the entry node s to any target node v. By definition, a node u is in the dominator set of v if every path from s to v passes through u. Since there's only one path here, the dominator set of v is exactly all nodes along this unique path from s to v (including s and v itself).

Step-by-Step Implementation #

Here are two straightforward methods, both with time complexity way better than O(m log n):

• Parent Pointer Traversal (Fastest Option)
  If your tree is rooted at s and each node stores its direct parent pointer:

  1. Start at your target node v.
  2. Traverse upwards by following parent pointers until you hit the entry node s.
  3. Collect every node you pass during this traversal—this is your dominator set.
  4. Time complexity: O(d), where d is the depth of v (length of the path from s to v). For most trees, this is drastically faster than Tarjan's algorithm.

• DFS/BFS Path Finding
  If you don't have parent pointers set up:

  1. Run a standard DFS or BFS starting from s, tracking the path to each node (use a stack or a parent-tracking array).
  2. Once you reach v, extract the full path from s to v that you tracked.
  3. This path is exactly the dominator set for v.
  4. Time complexity: O(n) in the worst case (e.g., a chain tree), but still way more efficient than building an entire dominator tree for a single node.

Quick Note for General Directed Graphs #

If you ever need to do this for a general directed graph (not a tree), there's still a lighter alternative to Tarjan's full dominator tree build:

1. First find all nodes reachable from s (call this set R), and all nodes that can reach v (call this set R').
2. Your candidate dominators are the intersection R ∩ R'—only these nodes could possibly dominate v.
3. For each candidate u, check if removing u disconnects s from v. If yes, u is in the dominator set.
   This avoids the overhead of building a full dominator tree, and can be faster for single-node queries depending on the graph structure.

For your tree-specific scenario though, the path-traversal method is optimal—simple to code, and with minimal runtime cost.

内容的提问来源于stack exchange，提问作者user11235