The gomory-hu tree of an undirected graph with capacities consists of a weighted tree that condenses information from all the*s-t cuts* for all s-t vertex pairs in the graph. Naively, one must think that $O(|V|^2)$ flow computations are needed to build this data structure, but actually it can be shown that only $|V| - 1$ flow computations are needed. Once the tree is constructed, we can get the minimum cut between two vertices*s* and*t* by querying the minimum weight edge in the unique*s-t* path.

The gomory-hu tree of an undirected graph$G$with capacities consists of a weighted tree that condenses information from all the*s-t cuts* for all s-t vertex pairs in the graph. Naively, one must think that $O(|V|^2)$ flow computations are needed to build this data structure, but actually it can be shown that only $|V| - 1$ flow computations are needed. Once the tree is constructed, we can get the minimum cut between two vertices*s* and*t* by querying the minimum weight edge in the unique*s-t* path.

We can say that two cuts $(X, Y)$ and $(U, V)$*cross* if all four set intersections $X \cap U$, $X \cap V$, $Y \cap U$, $Y \cap V$ are nonempty. Most of the work of the original gomory-hu method is involved in maintaining the noncrossing condition. The following simpler, yet efficient method, proposed by Gusfield uses crossing cuts to produce equivalent flow trees.

Lets assume the vertices are 0-indexed for the next section

The algorithm is composed of the following steps:

1. Create a (star) tree $T'$ on $n$ nodes, with node 0 at the center and nodes 1 through $n - 1$ at the leaves.

2. For $i$ from 1 to $n - 1$ do steps 3 and 4

3. Compute the minimum cut $(X, Y)$ in $G$ between (leaf) node $i$ and its (unique) neighbor $t$ in $T'$. Label the edge $(i, t)$ in $T'$ with the capacity of the $(X, Y)$ cut.

4. For every node $j$ larger than $i$, if $j$ is a neighbor of $t$ and $j$ is on the $i$ side of $(X, Y)$, then modify $T'$ by disconnecting $j$ from $t$ and connecting $j$ to $i$. Note that each node $j$ larger than $i$ remains a leaf in $T'$

It is easy to see that at every iteration, node $i$ and all nodes larger than $i$ are leaves in $T'$, as required by the algorithm.

The algorithm total complexity is $\mathcal{O}(V*MaxFlow)$, wich means that the overall complexity depends on the algorithm that was choosen to find the maximum flow.

- The method*solve* returns a list that contains for each index $i$ the cost of the edge connecting $i$ and its parent, and the parent number.

- Note that the algorithm doesn't produce a*cut tree*, only an*equivalent flow tree*, so one cannot retrieve the two components of a cut from the tree $T'$.

```{.cpp file=gomoryhu}

structgomory_hu {

struct edg{