Menu
Union-Find and DFS could be both used to find connectivity. Which one is better in which condition?
380
Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path between any two pair of vertices.
Note: From my Java submission results the optmized DSU solutions is the fastest solution at 10 ms, probably because it uses int[] instead of the Map objects in the DFS solutions below.
A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset. Union: Join two subsets into a single subset.
Using link-by-size, any UNION or FIND operation takes O(log n) time in the worst case, where n is the number of elements.
The union-find algorithm is best suited for situations where the equivalence relationship is changing, i.e., there are "Union" operations which need to be performed on your set of partitions. Given a fixed undirected graph, you don't have the equivalence relationships changing at all - the edges are all fixed. OTOH, if you have a graph with new edges being added, DFS won't cut it. While DFS is asymptotically faster than union-find, in practice, the likely deciding factor would be the actual problem that you are trying to solve.
tl;dr - Static graph? DFS! Dynamic graph? Union-find!
65
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
