Hopcroft-Karp Algorithm: Complexity Analysis and Applications

Introduction and Core Concepts

The hopcroft-karp algorithm is the most efficient classical algorithm for finding a maximum cardinality matching in a bipartite graph. Published by John Hopcroft and Richard Karp in 1973, it dramatically improved upon the naive augmenting path approach and remains the theoretical and practical standard for unweighted bipartite matching. If you work with assignment problems, resource allocation, or any system that pairs two distinct sets of entities, understanding this algorithm is essential.

A bipartite graph G = (U ∪ V, E) consists of two disjoint vertex sets U and V where every edge connects a vertex in U to a vertex in V. There are no edges within U or within V. A matching is a subset of edges M ⊆ E such that no two edges in M share a common vertex. A maximum matching is a matching of the largest possible cardinality, while a maximum cardinality matching maximizes the number of matched pairs. The hopcroft-karp algorithm solves exactly this problem for unweighted graphs, as opposed to the assignment problem where edges have weights.

Why does this matter? Many real-world problems are naturally bipartite. Consider matching job applicants to open positions, students to schools, donors to recipients, or web requests to servers. A naive greedy algorithm can easily get stuck in a suboptimal matching, leaving many vertices unmatched even when a perfect matching exists. The hopcroft-karp algorithm guarantees optimality while achieving a worst-case time complexity of O(E√V), which is significantly faster than the O(VE) bound of the simpler Kuhn algorithm based on depth-first search. This sub-quadratic dependence on vertices makes it scalable to graphs with millions of edges, which is why it is implemented in major graph libraries like NetworkX, Boost Graph Library, and LEDA.

Key Terminology

To understand the hopcroft-karp algorithm, you must be familiar with a few core concepts. A free or unmatched vertex is one that is not incident to any edge in the current matching. An alternating path alternates between edges in the matching and edges not in the matching. An augmenting path is an alternating path that starts and ends at free vertices. The key theorem by Claude Berge states that a matching is maximum if and only if there is no augmenting path with respect to it. Therefore, the entire goal of any matching algorithm is to repeatedly find and augment along such paths.

The hopcroft-karp algorithm distinguishes itself by finding a maximal set of shortest augmenting paths simultaneously in each phase, rather than finding a single augmenting path at a time. This batch processing is the source of its efficiency. It uses a breadth-first search (BFS) to build a layered graph of shortest augmenting paths and then a depth-first search (DFS) to find and augment along a maximal set of vertex-disjoint paths within those layers.

How It Works

The hopcroft-karp algorithm operates in phases, each consisting of two stages: BFS and DFS. It starts with an empty matching and iteratively improves it until no augmenting path remains. The use of a dummy NIL vertex that represents a free vertex is a common implementation trick to simplify BFS layering.

Unlike the simple augmenting path algorithm that might find a long augmenting path of length O(V) in one iteration, Hopcroft-Karp ensures that each phase finds only the shortest augmenting paths available. After augmenting along all shortest paths, the length of the shortest augmenting path strictly increases. Since the shortest augmenting path can increase at most O(√V) times before the matching becomes maximum, the number of phases is bounded.

Phase 1: BFS Layering to Build the Level Graph

The BFS stage constructs a layered directed graph starting from all free vertices in U. It explores edges in a specific way: from a free vertex in U, it follows unmatched edges to V, and from a matched vertex in V, it follows only the matched edge back to U. This alternating traversal ensures that any path discovered corresponds to an alternating path. Each vertex is assigned a distance or level, which is its distance from the nearest free vertex in U.

The BFS stops when it reaches free vertices in V. The distance to the first free vertex in V discovered determines the length of the shortest augmenting path in the current phase. All vertices beyond that distance are not included in the level graph. This creates a directed acyclic graph (DAG) that contains all shortest augmenting paths. If no free vertex in V is reachable, then no augmenting path exists and the algorithm terminates with a maximum matching.

Phase 2: DFS to Find a Maximal Set of Vertex-Disjoint Paths

Once the level graph is built, the algorithm runs DFS from each free vertex in U to find augmenting paths that respect the layering. That is, a DFS step from U to V or V to U is only allowed if it goes to the next layer (distance increases by exactly one). This constraint guarantees that only shortest augmenting paths are considered.

Crucially, the DFS finds a maximal set of vertex-disjoint augmenting paths. When a path is found, its vertices are marked as used for this phase and will not be reused, ensuring disjointness. Augmenting along this set flips the status of edges along each path: matched edges become unmatched and unmatched edges become matched, increasing the size of the matching by one for each path found. After all DFS searches complete, the algorithm returns to the BFS phase to recompute layers based on the new, larger matching.

Why Batch Augmentation Matters

The power of the hopcroft-karp algorithm lies in this batching. A single DFS-based algorithm might find one augmenting path per O(E) search, requiring up to O(V) augmentations. Hopcroft-Karp finds many shortest paths in a single O(E) DFS phase. The proof of the O(E√V) bound relies on two facts: after √V phases, the matching is close to optimal (at most √V augmentations remain), and each phase costs O(E). Thus the total work is balanced optimally between many short phases and a few final single-path augmentations.

Implementation

Implementing the hopcroft-karp algorithm efficiently requires careful handling of adjacency lists, pairing arrays, and distance labels. The standard implementation maintains two arrays, pairU and pairV, where pairU[u] stores the vertex in V matched to u (or NIL/-1 if free) and pairV[v] stores the vertex in U matched to v. A distance array dist is used only for vertices in U plus a sentinel NIL node.

Below is a conceptual naive implementation for comparison, followed by the full Hopcroft-Karp implementation. Note how the naive version finds one path at a time, while the optimized version uses BFS layering.

# Naive Kuhn DFS augmenting path algorithm - O(VE)
# Used as baseline to understand Hopcroft-Karp improvement
def kuhn_dfs(u, adj, visited, match_v):
    for v in adj[u]:
        if visited[v]:
            continue
        visited[v] = True
        # If v is free or we can reassign its current match
        if match_v[v] == -1 or kuhn_dfs(match_v[v], adj, visited, match_v):
            match_v[v] = u
            return True
    return False

def max_matching_kuhn(adj, n_left, n_right):
    match_v = [-1] * n_right
    result = 0
    for u in range(n_left):
        visited = [False] * n_right
        if kuhn_dfs(u, adj, visited, match_v):
            result += 1
    return result, match_v

The naive algorithm is simple but can be slow on dense graphs because it restarts DFS from each vertex without global layering. The Hopcroft-Karp implementation below adds BFS to find all shortest paths at once.

from collections import deque

class HopcroftKarp:
    def __init__(self, adj, n_left, n_right):
        # adj[u] = list of v neighbors for u in U (0-indexed)
        self.adj = adj
        self.n_left = n_left
        self.n_right = n_right
        self.NIL = -1
        self.INF = 10 ** 9
        self.pair_u = [-1] * n_left   # pair_u[u] = matched v or -1
        self.pair_v = [-1] * n_right  # pair_v[v] = matched u or -1
        self.dist = [0] * n_left

    def bfs(self):
        queue = deque()
        for u in range(self.n_left):
            if self.pair_u[u] == self.NIL:
                self.dist[u] = 0
                queue.append(u)
            else:
                self.dist[u] = self.INF
        
        dist_nil = self.INF
        
        while queue:
            u = queue.popleft()
            if self.dist[u] < dist_nil:
                for v in self.adj[u]:
                    pu = self.pair_v[v]
                    # If v is free, we found shortest path length
                    if pu == self.NIL:
                        dist_nil = self.dist[u] + 1
                    elif self.dist[pu] == self.INF:
                        self.dist[pu] = self.dist[u] + 1
                        queue.append(pu)
        return dist_nil != self.INF

    def dfs(self, u):
        for v in self.adj[u]:
            pu = self.pair_v[v]
            # Follow only edges that respect BFS layering
            if pu == self.NIL or (self.dist[pu] == self.dist[u] + 1 and self.dfs(pu)):
                self.pair_u[u] = v
                self.pair_v[v] = u
                return True
        # No augmenting path from u in this layer graph
        self.dist[u] = self.INF
        return False

    def max_matching(self):
        matching = 0
        while self.bfs():
            for u in range(self.n_left):
                if self.pair_u[u] == self.NIL:
                    if self.dfs(u):
                        matching += 1
        return matching

# Example driver for Hopcroft-Karp on a small bipartite graph
# U = {0,1,2,3}, V = {0,1,2,3}
# Edges: 0-0, 0-1, 1-1, 1-2, 2-2, 2-3, 3-0

adj = [
    [0, 1],  # U0 connects to V0, V1
    [1, 2],  # U1 connects to V1, V2
    [2, 3],  # U2 connects to V2, V3
    [0]      # U3 connects to V0
]

hk = HopcroftKarp(adj, n_left=4, n_right=4)
size = hk.max_matching()
print(f"Maximum matching size: {size}")  # Expected 4
print(f"pair_u (U -> V): {hk.pair_u}")
print(f"pair_v (V -> U): {hk.pair_v}")

# Verify matching is valid and maximal
def verify_matching(pair_u, pair_v):
    used_v = set()
    for u, v in enumerate(pair_u):
        if v != -1:
            assert v not in used_v, "V vertex matched twice"
            assert pair_v[v] == u, "Inconsistent pairing"
            used_v.add(v)
    print("Matching verified: vertex-disjoint and consistent")

verify_matching(hk.pair_u, hk.pair_v)

# Optimized Hopcroft-Karp for large sparse graphs
# Uses adjacency as dict of sets and iterative stack to avoid recursion limits
from collections import deque

def hopcroft_karp_optimized(adj, n_left, n_right):
    pair_u = [-1] * n_left
    pair_v = [-1] * n_right
    dist = [0] * n_left
    INF = 10 ** 9

    def bfs():
        q = deque()
        for u in range(n_left):
            if pair_u[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = INF
        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                pu = pair_v[v]
                if pu == -1:
                    found = True  # reachable free vertex in V
                elif dist[pu] == INF:
                    dist[pu] = dist[u] + 1
                    q.append(pu)
        return found

    def dfs(u):
        # Iterative DFS using explicit stack to avoid recursion depth issues
        stack = [(u, 0)]  # (current u, next neighbor index)
        path = []  # stores (u, v) edges in current path
        while stack:
            curr_u, idx = stack[-1]
            if idx >= len(adj[curr_u]):
                dist[curr_u] = INF
                stack.pop()
                if path and path[-1][0] == curr_u:
                    path.pop()
                continue
            v = adj[curr_u][idx]
            stack[-1] = (curr_u, idx + 1)
            pu = pair_v[v]
            if pu == -1:
                # Found augmenting path - augment along path + (curr_u, v)
                path.append((curr_u, v))
                for pu_u, pv_v in path:
                    pair_u[pu_u] = pv_v
                    pair_v[pv_v] = pu_u
                return True
            elif dist[pu] == dist[curr_u] + 1:
                path.append((curr_u, v))
                stack.append((pu, 0))
        return False

    matching = 0
    while bfs():
        for u in range(n_left):
            if pair_u[u] == -1 and dfs(u):
                matching += 1
    return matching, pair_u, pair_v

The first two code blocks show the classic recursive implementation, which is clear and sufficient for most competitive programming and interview settings. The fourth block demonstrates a production-ready iterative variant that avoids Python recursion limits on deep graphs with thousands of vertices and handles sparse adjacency efficiently.

Step-by-Step Example

Let us walk through the hopcroft-karp algorithm on a concrete bipartite graph to make the BFS and DFS phases tangible. Consider U = {A, B, C, D} and V = {1, 2, 3, 4} with edges: A-1, A-2, B-2, B-3, C-3, C-4, D-1. This graph has a perfect matching of size 4, but a greedy algorithm might fail to find it.

Initially, the matching M is empty. All vertices in U are free. BFS starts by enqueueing A, B, C, D with distance 0. From these, it explores unmatched edges to V. Since M is empty, all edges are unmatched. BFS discovers V vertices 1, 2, 3, 4 at distance 1. Because free vertices in V are reached immediately, dist_nil = 1. The level graph consists of all U vertices at layer 0 and all V vertices at layer 1.

DFS now runs from each free U vertex. From A, DFS can go to 1 (free) and immediately augment: A-1 becomes matched. From B, DFS tries 2 (free) and augments B-2. From C, it augments C-3 or C-4, say C-3. From D, the only neighbor 1 is already matched to A, but DFS respects layering: since dist[pairV[1]] = dist[A] = 0, and dist[A] is not equal to dist[D] + 1 (0 != 1), the edge D-1 is not in the level graph for this phase. So D remains free after phase 1. Matching size is now 3: {A-1, B-2, C-3}.

Phase 2 begins with free vertices: U = {D}, V = {4}. BFS from D (dist 0) follows unmatched edge D-1 to V1 (dist 1). V1 is matched to A, so it follows the matched edge V1-A to U vertex A, setting dist[A] = 2 and enqueueing A. From A, BFS follows unmatched edge A-2 to V2 (dist 3). V2 is matched to B, so BFS goes to B with dist 4. From B, unmatched edge B-3 leads to V3 matched to C, so C gets dist 6. From C, unmatched edge C-4 leads to free vertex V4. Thus dist_nil = 7, and the shortest augmenting path length is 7 edges (3 unmatched + 2 matched + etc.). The level graph is a chain: D -1- A -2- B -3- C -4.

DFS from D now follows this unique layered path: D-1-A-2-B-3-C-4. Augmenting along it flips all edges: D-1 becomes matched, A-1 becomes unmatched, A-2 becomes matched, B-2 becomes unmatched, B-3 becomes matched, C-3 becomes unmatched, C-4 becomes matched. The final matching is {D-1, A-2, B-3, C-4} of size 4, which is maximum. No free vertex in U can reach a free vertex in V in the next BFS, so the algorithm terminates.

This example illustrates two critical properties: first, a vertex that was matched early (A-1) can be rematched to allow a globally larger matching, and second, the length of the shortest augmenting path increased from 1 to 7 between phases, demonstrating the monotonic increase that bounds the number of phases.

Complexity Analysis

The hopcroft-karp algorithm is celebrated for its O(E√V) worst-case time complexity, where E is the number of edges and V is the total number of vertices (V = |U| + |V|). This bound is significantly better than the O(VE) bound of the naive Kuhn algorithm when the graph is large. The analysis hinges on the phase structure and the concept of symmetric difference between matchings.

Each BFS and DFS phase together costs O(E) time. BFS visits each edge at most once while building layers, and DFS also traverses each edge at most once per phase because vertices that are found to be dead ends are removed from the level graph (dist set to INF). Therefore, the cost per phase is linear in the number of edges.

The number of phases is bounded by O(√V). The proof considers that after √V phases, the shortest augmenting path has length at least √V. Any augmenting path must use at least √V vertices, so the symmetric difference between the current matching and an optimal matching can contain at most √V vertex-disjoint augmenting paths. Thus at most √V additional single-path augmentations are needed. Formally, if M is the current matching and M* is a maximum matching, then |M*| - |M| ≤ |V| / (length of shortest augmenting path). When that length exceeds √V, the remaining gap is ≤ √V.

Space complexity is O(V + E) to store the graph adjacency lists, the pairing arrays, and the distance array. For sparse graphs where E is close to V, this is very efficient. For dense graphs where E = O(V²), the algorithm still runs in O(V²·⁵), which is better than O(V³) alternatives.

In the best case, such as when the graph already has a perfect matching that is found in the first phase because all shortest paths are length 1 and vertex-disjoint, the algorithm can finish in O(E) time. In practice, on random bipartite graphs, the number of phases is often much smaller than √V, typically under 10 even for graphs with thousands of vertices, making average performance nearly linear.

It is important to note that the O(E√V) bound assumes an adjacency list representation. If an adjacency matrix is used, the BFS/DFS would cost O(V²) per phase, degrading the total to O(V²·⁵). Always use adjacency lists or compressed sparse row formats for large graphs.

Variations and Optimizations

While the classic hopcroft-karp algorithm is optimal for unweighted bipartite matching, several variations and optimizations adapt it to different constraints and hardware.

One common optimization is early termination and scaling for unbalanced bipartite graphs. If |U| is much smaller than |V|, the bound can be tightened to O(E√|U|). Implementations can choose to run BFS from the smaller side to minimize work. Another practical speedup is to use a greedy initialization: before starting Hopcroft-Karp phases, run a fast greedy matching that matches each free U vertex to any free V neighbor. This often finds 80-90% of the maximum matching in O(E) time and dramatically reduces the number of phases needed.

Weighted and Dynamic Variants

The standard hopcroft-karp algorithm does not handle weighted edges. For assignment problems where each edge has a cost or profit, the Hungarian algorithm (O(V³)) or successive shortest augmenting path with potentials (O(VE log V)) is required. However, there is a variant called Hopcroft-Karp for maximum weight matching in bipartite graphs that combines scaling techniques to achieve O(E√V log V) for integer weights, though it is more complex to implement.

For dynamic graphs where edges are inserted or deleted over time, fully recomputing the matching is wasteful. Dynamic matching algorithms maintain the matching incrementally, often using a variant of Hopcroft-Karp that only recomputes BFS layers in the affected region. Similarly, for online bipartite matching where vertices in V arrive one by one, the Karp-Vazirani-Vazirani randomized algorithm is used, which is different but inspired by the same augmenting path ideas.

Parallel and GPU Implementations

The BFS phase is highly parallelizable because all free vertices are processed simultaneously. Modern parallel implementations use breadth-first frontier expansion with atomic operations or use the Bulk Synchronous Parallel model. The DFS phase is harder to parallelize due to the need for vertex-disjointness, but techniques like DFS with greedy path stripping or using maximal independent sets can help. On GPUs, implementations often replace DFS with a parallel BFS-based augmenting path search using techniques from the push-relabel framework.

Memory optimizations include using bitsets for dense subgraphs, using 32-bit integers for pair arrays when V < 2³¹, and storing adjacency in a single flat array with offsets (CSR format) to improve cache locality. For very large graphs that do not fit in RAM, external-memory Hopcroft-Karp variants use disk-based BFS with semi-external structures.

Real-World Applications

The hopcroft-karp algorithm is not just a theoretical curiosity; it powers many systems where optimal pairing is critical. Its ability to guarantee maximum cardinality with good scalability makes it the default choice whenever the problem can be modeled as unweighted bipartite matching.

In web servers and load balancers, requests (U) must be assigned to backend servers (V) where each server can handle one request at a time and not all servers can handle all request types due to locality or capability constraints. Finding a maximum matching maximizes throughput. Similarly, in content delivery networks, the algorithm matches users to edge caches to maximize cache hits while respecting capacity constraints (extended to b-matching where servers have capacities > 1).

In databases, the hopcroft-karp algorithm is used for query optimization and entity resolution. When joining two tables on a non-unique key, finding a maximum matching helps identify duplicate records or optimal join orders. In data deduplication, bipartite matching between records from two sources determines the largest set of unique entities that can be merged without conflicts.

Network flow and telecommunications rely heavily on bipartite matching. Assigning frequencies to cell towers, wavelengths to optical paths, or time slots to communication channels can all be modeled as bipartite graphs. The algorithm also forms the basis for more general flow algorithms: any bipartite matching can be reduced to max flow by adding a source and sink, and Hopcroft-Karp is essentially a specialized Dinic's algorithm for unit-capacity bipartite networks.

Beyond these, the hopcroft-karp algorithm is used in compiler register allocation (variables vs registers), recommendation systems (users vs items for diverse recommendations), and even in solving puzzles like Sudoku, where cells are matched to possible values. Its versatility stems from the ubiquity of bipartite structures.

Comparison with Alternatives

Choosing the right matching algorithm depends on graph type, edge weights, and performance requirements. The hopcroft-karp algorithm is optimal for unweighted bipartite graphs, but other algorithms are better suited for different scenarios.

The naive augmenting path algorithm (often called Kuhn's algorithm) is simpler to implement and can be faster on very small or very sparse graphs due to lower constant factors, but it degrades to O(VE) on dense graphs. The Hungarian algorithm solves the weighted assignment problem where each edge has a cost and you want minimum total cost perfect matching, but it is overkill and slower if you only need maximum cardinality. For general graphs that are not bipartite (where edges can be within a single set), Edmonds' Blossom algorithm is required, which handles odd cycles.

Another alternative is to reduce bipartite matching to maximum flow and run Dinic's algorithm. In fact, Hopcroft-Karp can be viewed as Dinic's algorithm specialized for unit-capacity bipartite networks with O(E√V) instead of Dinic's O(E·min(V²ᐟ³, √E)) for unit networks. For most practitioners, using a max flow library is acceptable, but a dedicated Hopcroft-Karp implementation will be faster and use less memory.

In practice, if your graph is bipartite and unweighted and has more than a few hundred vertices, Hopcroft-Karp is the clear winner. If you need weights, use Hungarian or successive shortest path. If your graph is not bipartite, you must use Blossom. Many standard libraries automatically select Hopcroft-Karp when they detect an unweighted bipartite input.

Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the hopcroft-karp algorithm, leading to incorrect results or performance degradation. Understanding these pitfalls is crucial for both interviews and production code.

A frequent mistake is not correctly handling the NIL sentinel and distance initialization. The BFS must initialize distances for all free vertices in U to 0 and all matched vertices to INF, and it must track dist_nil separately. Forgetting to set dist[u] = INF when DFS fails from u causes the same dead-end vertex to be revisited in the same phase, leading to O(VE) behavior instead of O(E√V). Another common bug is allowing DFS to traverse edges that do not respect the BFS layering (dist[pairV[v]] != dist[u] + 1), which can find non-shortest augmenting paths and break the phase invariant.

Another pitfall is using recursion for DFS without considering Python's recursion limit. On graphs where augmenting paths can be O(V) long (e.g., a long chain), recursive DFS can hit recursion depth errors or stack overflow. The iterative stack-based DFS shown earlier avoids this. Additionally, developers sometimes use adjacency matrices or repeatedly scan all V vertices to find neighbors, which turns O(E) phases into O(V²) phases. Always use adjacency lists and iterate only over actual neighbors.

Best practices include: first, run a greedy pre-matching to reduce phases; second, represent vertices with 0-based contiguous integers for fast array indexing; third, use deque for BFS and avoid expensive Python object overhead inside the inner loop; fourth, test on edge cases such as empty graphs, graphs with no edges, graphs that are already perfectly matched, and unbalanced graphs where |U| != |V|. Finally, always verify the result by checking that no two matched edges share a vertex and that no augmenting path remains (you can run one more BFS to confirm no free V is reachable).

For performance, consider using PyPy or C++ for very large graphs, as Python loops can be slow for E > 10⁶. In Python, using Numba or Cython to compile the BFS/DFS loops can yield 10-50x speedups. If you are in an interview, clearly state the assumptions: bipartite, unweighted, and that you are finding maximum cardinality, not maximum weight.

Interview Questions

Interviewers frequently test understanding of the hopcroft-karp algorithm through conceptual questions, complexity analysis, and coding tasks. Here are common questions and how to approach them.

1. Why does Hopcroft-Karp achieve O(E√V) while naive DFS is O(VE)?

Answer: Naive DFS finds one augmenting path per O(E) search and may need O(V) augmentations. Hopcroft-Karp finds a maximal set of shortest augmenting paths per phase in O(E) and guarantees that the length of the shortest augmenting path strictly increases each phase. After √V phases, the remaining augmentations are at most √V, so total phases are O(√V). Emphasize the batch processing and the monotonic increase in path length, and mention the symmetric difference argument.

2. How would you check if a bipartite graph has a perfect matching using Hopcroft-Karp?

Answer: Run Hopcroft-Karp to find a maximum matching. If the size equals min(|U|, |V|) and |U| == |V|, then a perfect matching exists. If |U| != |V|, a perfect matching is impossible, but you can check if all vertices on the smaller side are matched (i.e., matching size == min(|U|, |V|)). This is O(E√V). You can also mention Hall's Marriage Theorem as the theoretical condition, but algorithmic verification is via Hopcroft-Karp.

3. Can Hopcroft-Karp be used for weighted bipartite matching?

Answer: No, directly it cannot. It finds maximum cardinality, not maximum weight. For weighted cases, you need the Hungarian algorithm for assignment (perfect matching with minimum cost) or the successive shortest augmenting path algorithm with potentials for maximum weight matching. You could mention that there are weighted extensions of Hopcroft-Karp using scaling, but they are not the standard algorithm. This tests whether you confuse cardinality vs weight.

4. Implement Hopcroft-Karp and explain the role of BFS and DFS.

Answer: Provide the code as shown in the Implementation section, and explain that BFS builds the level graph containing all shortest augmenting paths and determines if any augmenting path exists, while DFS finds a maximal set of vertex-disjoint augmenting paths within that level graph and augments the matching. Be ready to walk through the example graph and explain why DFS must respect dist[pairV[v]] == dist[u] + 1 and why you set dist[u] = INF on failure.

5. How do you reduce bipartite matching to max flow, and how does Hopcroft-Karp relate to Dinic's algorithm?

Answer: Add a source S connected to all vertices in U with capacity 1, direct all original edges from U to V with capacity 1, and connect all vertices in V to a sink T with capacity 1. The max flow from S to T equals maximum matching size. Dinic's algorithm on this unit network also runs in O(E√V), and Hopcroft-Karp is essentially Dinic's specialized for bipartite unit networks where BFS builds the level graph and DFS sends blocking flows. This shows deep understanding of the connection between matching and flow.