2. Why the plain DFS is wasteful: surviving fragments

The whole motivation for link-cut trees, worked out on a level-graph picture 3:33.

The level graph and the naive routine

In the level graph every edge goes from one level to the very next level — nothing else is kept 3:51.
Naive routine: DFS from s toward t; on reaching t, augment along the path by its minimum residual capacity and subtract that from every edge on it; then DFS again from s 4:15.
Each augment saturates at least one edge (possibly more), and saturated edges are deleted 5:07.

After an augment, the unsaturated edges of the explored path survive, but the next DFS re-walks them from s step by step 5:36, 6:34.
If a data structure remembered those live edges, the search could jump straight to the far end of the surviving fragment instead of re-DFSing it, then continue (or retreat and kill it) from there 7:14, 8:03.
That "remember the live fragments and skip ahead" idea is exactly what link-cut trees support 8:03.

Once a middle edge saturates, what survives can branch — the leftover fragment is a tree, not a path 8:40, 9:14.
Hence the data structure must maintain a collection of vertex-disjoint rooted trees 9:14, 9:47.

Student question: why is the maintained structure always a tree rather than a DAG? 11:49
Answer: the algorithm never ignores an existing path — the first thing every loop iteration does is find-root(s), which jumps to the end of the path already leaving s; a new path is only explored once the existing one dead-ends 12:16, 13:04, 13:41.
Cycling back is impossible anyway: the underlying level graph is itself a DAG whose edges only go forward one level 14:14, 14:38.
Invariant: the maintained graph is always a forest of rooted trees 15:18.