### Benq's blog

By Benq, history, 2 years ago,

Does anyone have a $O(V^2)$ solution to this problem (available here)? The spoiler describes one but I don't understand what it means when it says to "search for this path backwards," and I can't find a model solution. (However, an $O(EV)$ solution with bitset did pass ...)

• +50

 » 2 years ago, # |   -49 Send \$5500 and I'll help!
 » 2 years ago, # |   +11 Not even one can answer Benq Question! Benqosity
 » 2 years ago, # | ← Rev. 2 →   +39 I don't have an easy solution, but the following paper provide (somewhat sophisticated) $O(V^2)$ solutions: EDGE-DISJOINT SPANNING TREES, DOMINATORS, AND DEPTH-FIRST SEARCH by Robert E. Tarjan solves the problem in $O(V \log V + E)$ using dfs (the algorithm also computes the dominator tree). A Matroid Approach to Finding Edge Connectivity and Packing Arborescences by Harold N. Gabow solves the problem of finding $k$ edge-disjoint Arborescences in $O(k^2 V^2)$. The algorithm is based on Matroid intersection theory and augmenting paths (and I don't know much about those topics).
•  » » 2 years ago, # ^ |   +4 Thanks!
•  » » 22 months ago, # ^ |   +10 There is a simplified document for the second paper. It also claims to run in $O(kE \log V)$. Shoutout to rpengsoo. Link