Connectivity and Topological Order
Which vertices reach which, in which direction, and which single vertex or edge is holding the graph together.
Union-Find: Path compression at work
Without direction, connectivity is a yes or no about reachability, and one traversal per unvisited vertex answers it. Direction changes the question entirely: u reaching v says nothing about v reaching u, so the right unit becomes the strongly connected component, a maximal set in which every vertex reaches every other. Contract each component to a single point and what remains is always acyclic.
A directed acyclic graph has a topological order, a listing in which every edge points forward. Kahn's algorithm builds one by repeatedly taking a vertex whose in-degree has fallen to zero. The DFS version takes the reverse of the order in which vertices finish. Both run in O(V + E) and both double as a cycle test, because a graph with a cycle has no such order: Kahn ends with vertices it could never place, DFS meets an edge back into the path it is still on.
The last group asks what a graph would survive. One DFS records, per vertex, its discovery time and the earliest discovery time reachable from its subtree without going back up the tree edge, the low-link. Comparing the two gives bridges, low[v] > disc[u], and articulation points, low[v] >= disc[u], in a single O(V + E) pass, and with a stack the same numbers give Tarjan's strongly connected components. Union-find answers the incremental version instead: edges arrive one at a time and the only question is whether two vertices are already joined, at near constant cost per operation.
After this you can
- Produce a topological order two different ways and use either one to detect a cycle
- Explain why reachability in a directed graph needs strongly connected components
- Read discovery times and low-links to name the bridges and the articulation points
- Choose union-find when edges arrive over time and a DFS when the graph is already fixed
In this order
Where people go wrong
Undirected habits on a directed graph
Running one DFS and calling everything it touched a component is only valid without direction. In a directed graph that set is what the start vertex reaches, which can be the entire graph while nothing at all reaches back. Two passes (Kosaraju) or low-links (Tarjan) are what actually answer it.
Union-find with only half the optimisations
Path compression flattens the tree during find, union by size keeps it shallow in the first place, and the near constant amortised cost needs both. Hanging an arbitrary root under the other with no compression builds a chain and puts find back at O(n).
Treating bridges and articulation points as the same thing
The two tests differ by one sign, and so do the answers. An endpoint of a bridge with degree one is not an articulation point, and two cycles sharing a single vertex give an articulation point with no bridge anywhere near it.