Connectivity and Topological Order
Which vertices reach which, in which direction, and which single vertex or edge is holding the graph together.
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
find(0): parent[0] = 0, so 0 is a root already. Its set is 0.
In this order
- Union-Find Operationsfind climbs to the root then flattens the path; union hangs the smaller root under the larger.
- Kahn's AlgorithmRepeatedly place a vertex with in-degree zero and lower the counts of everything it points to.
- DFS Topological SortReverse postorder of a DFS is a topological order, and a back edge means there is none.
- Strongly Connected ComponentsMaximal sets where every vertex reaches every other; the condensation is a DAG.
- KosarajuFinish order from one DFS, reverse every edge, then DFS from the latest finisher to paint each component.
- Tarjan SCCPush on entry, lower low-links through open vertices, pop a whole component when low[u] == disc[u].
- BridgesOne DFS with discovery times and low-links; a tree edge u-v is a bridge when low[v] > disc[u].
- Articulation PointsA vertex is an articulation point when some DFS child has low[v] >= disc[u], or it is the root with two subtrees.
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.
Or a different category
Graph Traversal
The graph is undirected and you only need to visit everything reachable or count the pieces; one BFS or DFS per unvisited vertex is enough.
Dynamic Programming
The topological order is only a means to an end and the real work is accumulating a value along the DAG, such as longest path or number of routes.