Beau

Alright Jo, so last time we were deep in trees with HLD and Centroid Decomposition, which was… a lot. But I feel like the final boss of so many of these hard problems is always network flow. It just feels… denser.

Jo

It is. It’s a different kind of complexity. With trees, the structure is rigid. With flows, you're dealing with this… dynamic system. Stuff is moving, capacities are changing. The state isn't static. And that's where the implementation details really, really matter.

Beau

Yeah, let's talk about those. I mean, everyone learns the high-level idea of Dinic's algorithm, right? Build a level graph with BFS, find augmenting paths with DFS, repeat. But when you look at a top-tier template, the code doesn't always map cleanly to that simple loop.

Jo

Exactly. The first thing that trips people up is managing the residual graph. It's not like you're building a new graph every single iteration. You have one graph structure, and the 'capacities' on the edges are what change. The key is how you represent the reverse edges.

Beau

Okay, so let's get concrete. In a lot of templates, you see something like `add_edge(u, v, capacity)`. But it’s not just one edge being added, is it?

Jo

Correct. You add the forward edge from u to v with the given capacity, and you also add a reverse edge from v to u with an initial capacity of zero. The trick is to make them know about each other. So when you store your edges in an array, say at index `i` and `i+1`, the edge at `i`'s reverse is `i+1`, and `i+1`'s reverse is `i`. You can get the reverse of any edge `e` by just XORing its index with 1. It's super fast.

Beau

Ah, that's the `i^1` thing I always see. So when you push, say, 5 units of flow from u to v, you decrease the capacity of the forward edge by 5, and you *increase* the capacity of the reverse edge by 5.

Jo

Precisely. That's the 'undo' mechanism. It's like saying, 'I've sent 5 units this way, so now there's an option to send 5 units back to cancel it out.' That's the whole concept of the residual graph, but implemented in place, without creating any new data structures. It's all just capacity updates.

Beau

And this brings up the graph representation itself. We talked before about global arrays vs `std::vector` for speed. In these flow templates, I never see `vector<vector<pair<int, int>>>`. It's always this `head` and `next` array structure. Why that specific choice?

Jo

Cache locality. It's a linked list, but implemented inside a giant array. Your edges are all stored contiguously in memory in one big block. When you iterate through a node's neighbors, you're just following pointers within that block. `std::vector` for an adjacency list means each node's neighbor list is a separate memory allocation, potentially scattered all over the heap. When your DFS is trying to find paths, jumping between those memory locations can cause cache misses, which costs you precious nanoseconds.

Beau

So it's a 'mental movie' of... instead of having a bunch of separate little address books for each person's contacts, you have one giant phonebook for everyone. And for each person, you just note 'their first contact is on page 50, and after that, see page 112,' and so on. The CPU can just load a huge chunk of the phonebook at once.

Jo

That's a perfect analogy. And it also avoids the overhead of memory allocation during the run. You allocate one big array for all possible edges at the start, and that's it. No `push_back` calls that might trigger a resize and copy. In a tight time limit, that matters.

Beau

Okay, that makes sense. Now, let's talk about bipartite matching. I know you can solve it with a flow network. You create a source `S` and a sink `T`. You connect `S` to all nodes on the left side, and all nodes on the right side to `T`, all with capacity 1. Then for each original edge between left and right, you add an edge with capacity 1.

Jo

Right. And the max flow from `S` to `T` is the size of the maximum matching. But if you're just doing unweighted bipartite matching, Dinic's is… a bit of overkill. The structure of this 0-1 capacity graph is very special. The level graph will have a very specific form.

Beau

That's Hopcroft-Karp, isn't it? The one that's theoretically faster for this specific case.

Jo

It is. Hopcroft-Karp is basically a specialized version of Dinic's for these unit-capacity bipartite graphs. The core idea is the same: find augmenting paths. But instead of one DFS, it finds a *maximal set* of shortest augmenting paths in one go. You do a BFS to build levels, just like Dinic's, but then you do a single DFS pass that's allowed to find multiple, vertex-disjoint paths simultaneously.

Beau

Okay, so Dinic's DFS finds one path, pushes flow, and then has to start over from the source. Hopcroft-Karp's DFS can, what, find a path, and then kind of… resume from where it was to find another path that doesn't touch the first one?

Jo

Sort of. The DFS explores from all the unmatched nodes on the left side. When it finds an augmenting path for one of them, it marks the path as used and returns 'true'. The key is that the calling function doesn't stop. It just continues its loop and tries to start another DFS from the *next* unmatched left-side node in the same level-graph phase. Since the paths are vertex-disjoint, the earlier path doesn't invalidate the level graph for the later searches in the same phase.

Beau

So in practice, for competitive programming, if a problem is clearly bipartite matching, is it worth having a separate Hopcroft-Karp template? Or is a well-optimized Dinic's good enough?

Jo

Honestly, a good Dinic's is usually fine. The constant factors on a clean Dinic's implementation are often so good that it outperforms a sloppier Hopcroft-Karp. Plus, Dinic's is more general. If the problem suddenly adds capacities or becomes non-bipartite, your Dinic's code still works. Your Hopcroft-Karp code is useless.

Beau

Okay, one last thing: edge cases. What about multiple edges between the same two nodes, u and v? Or self-loops?

Jo

Self-loops are easy: they're useless for sending flow from a source to a sink, so you can just ignore them. For multiple edges, it depends. If you're using the head/next array representation, adding two edges from `u` to `v` just puts two distinct entries in your edge list. Dinic's will treat them as separate paths, which is perfectly fine. The 'mental movie' is having two separate pipes between two locations. Flow can go through both. You don't need to merge them.

Beau

So the implementation handles it naturally, as long as you don't try to be clever and aggregate them beforehand. The whole system is more robust than it seems.

Jo

It is. The beauty of these flow algorithms is that the low-level rules—updating residual capacities on forward and reverse edges—correctly handle the high-level complexity. You just need to trust the process and make sure your implementation of those low-level rules is bug-free and efficient.