# On Finding Optimal (Dynamic) Arborescences
## 4 Implementation Details and Analysis
### Disjoint Sets  
Two implementations of the union--find data structure for managing disjoint sets are used, with both supporting the standard operations. One is used to represent weakly connected components, while the other is employed for strongly connected components. The latter is an augmented version. In the case of the first implementation, the following common operations are supported: \(\texttt{WFIND}(x)\), which returns a pointer to the representative element of the unique set containing \(x\); \(\texttt{WUNION}(x)\), which unites the sets that contain \(x\) and \(y\); and \(\texttt{WMAKE-SET}(x)\), which creates a new set whose only element and representative is \(x\). For the augmented implementation, the same operations are supported, but they are named SFIND, SUNION, and SMAKE-SET; two extra operations are also supported, namely, SADD-WEIGHT and SFIND-WEIGHT, which are detailed below.  
Our implementations of the union--find data structure rely on the conventional heuristics, namely, union by rank and path compression, thereby achieving nearly constant time per operation in practice; \(m\) operations over \(n\) elements take \(O(m\alpha(n))\) amortized time, where \(\alpha\) is the inverse of the Ackermann [24]. Both implementations use two arrays of integers, namely, the rank and the parent array instead of pointer-based trees. Even though the operation's computational complexity is, theoretically speaking, the same, using arrays instead of pointers promotes memory locality, since arrays are allocated in contiguous memory.  
The purpose of having a different implementation for strongly connected components is to bring a constant time solution for the computation of the reduced costs, thereby exploiting the path compression and union by rank heuristics. While finding the minimum weight incident edges in every vertex in the contraction phase, cycles may arise. Then, the maximum weight edge in the cycle is found, the reduced costs are computed, and the weight of the incident edges is updated by summing the reduced costs. In this context, the augmented version of the union--find data structure then supports the following operations as mentioned above: \(\texttt{SADD-WEIGHT}(x,k)\), which adds a constant \(k\) to the weight of all the elements of the set containing \(x\), and \(\texttt{SFIND-WEIGHT}(x)\), which returns the accumulated _weight_ for the set containing \(x\). Supporting these operations requires an additional attribute _weight_, which is represented internally as a third array to store the weights. The weights are initialized with 0. The \(\texttt{SADD-WEIGHT}(x,k)\) operation adds value \(k\) to the root or representative element of the set containing \(x\) in constant time. The operation \(\texttt{SFIND}(x)\) has been rewritten for updating the weights whenever the underlying union--find tree structure changes due to the path compression heuristic; this change does not change the complexity of this operation. The operation \(\texttt{SFIND-WEIGHT}(x)\) performs the sum of all values stored in field _weight_ on the path from \(x\) until we meet the root of the disjoint set containing \(x\); the cost of this operation is identical to the cost of operation of \(\texttt{SFIND}\). A constant time solution is obtained then for updating the weight of all the elements in a given set, which allows us to update the weight of all the edges that are incident on a given vertex and also in constant time.