有向无环图多请求高效根查找：O(m log n)+O(n)复杂度方案问询

Great question! Let's walk through how to solve this efficiently, since your current approach is hitting unnecessary O(n²) complexity due to updating child nodes in bulk—and there's a far better way using a classic data structure with path compression.

First, let's clarify the structure of your graph: since every node has at most one parent, your graph is a forest of rooted trees (each tree's root has no parent, all other nodes have exactly one parent). Adding an edge (u, v) is only valid if:

1. v is a root (no existing parent), and
2. Adding u→v won't create a cycle—which in this structure only happens if u is already in v's subtree (i.e., the root of u is v itself).

Union-Find (Disjoint Set Union, DSU) with path compression is perfect here—it's designed for dynamic connectivity problems like this, and path compression makes operations nearly constant-time.

Step-by-Step Implementation #

1. Initialization #

Create a parent array where each node starts as its own root:

parent = list(range(n + 1))  # Assuming nodes are 1-indexed

2. Find Operation (Get Root of a Node) #

This is the critical part—path compression ensures that after the first call, nodes point directly to their root, speeding up future queries:

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])  # Path compression: shortcut u directly to the root
    return parent[u]

• What this does: If u isn't its own parent, recursively find the root of u's parent, then update u's parent to point straight to that root. This flattens the tree over time, making subsequent queries faster.

3. Add Edge Operation #

Before adding the edge (u, v), validate the two conditions, then update the parent relationship:

def add_edge(u, v):
    root_v = find(v)
    root_u = find(u)
    # Check if v is a root and u isn't in v's subtree
    if root_v == v and root_u != root_v:
        parent[v] = u
        return True  # Edge added successfully
    return False  # Edge is invalid

4. Find Root Query #

To get the root of any node u, just call find(u)—it's the same as the Find operation above, with the same near-constant time complexity.

Complexity Analysis #

• Initialization: O(n) time to set up the parent array.
• Find Operation: Each call takes O(α(n)) time, where α is the inverse Ackermann function. This function grows extremely slowly—for all practical purposes (even n = 10^18), α(n) is less than 5, so it's effectively a constant.
• Add Edge Operation: Two Find calls (O(α(n)) total) plus an O(1) parent update.
• Overall: The total time complexity is O(m α(n) + n), which is even better than the O(m log n) you were targeting. If you need a bound in terms of log n, note that α(n) ≤ log* n (the iterated logarithm), which is still way smaller than log n for all real-world inputs.

Why This Beats Your Original Approach #

Your original solution required iterating over all children of v to update their root pointers every time you added an edge, leading to worst-case O(n²) time. With DSU and path compression, we eliminate this entirely:

• We don't need to maintain a children array at all.
• Path compression dynamically optimizes the path to the root on each Find call, so we never have to manually update large batches of nodes.

Optional Extensions #

If you need to track extra information (like node depth or subtree size), you can extend the DSU with additional arrays:

• Add a depth array to track how far a node is from its root.
• Add a size array to track the size of the subtree rooted at each node (though since your edge direction is fixed as u→v, union-by-size/rank isn't strictly necessary unless you want to optimize path compression further).

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