## Introduction

A matching of a maximum number of edges is called Maximum Matching. If any edge is added to a maximum matching, it is no longer matching. A Bipartite Graph may have more than one maximum matching.

This blog will discuss the problem of finding the Maximum Matching using the Hopcroft-Karp Algorithm. We will discuss this article in detail. Let's start going!

### Problem Statement

In this problem, we will take the Bipartite graph as input and find an augmented path. An augmented path is a path with free vertices as starting and ending points that alternates between matching and non-matching edges.

Let's look at the problem of finding the Maximum Matching using the Hopcroft-Karp Algorithm.

### Sample Examples

**Example 1:**

**Input:**

```
1 1
1 3
2 3
3 4
4 3
4 2
```

**Output:**

` 4`

Explanation:

In the above example, green edges show the maximum matching path.

**Example 2:**

**Input:**

```
2 3
3 1
1 2
```

**Output: **

`3`

Explanation:

In the above example, green edges show the maximum matching path.

## Approach

We will first find the Augmented Path, an alternative path between matching and non-matching edges, and add it to the existing matching path, which makes the previous matching edges non-matching and non-matching as matching.

The basic idea to find the augmented path is Breadth First Search. BFS traversal divides the edges into matching and non-matching.

### Algorithm

**1️⃣** Set Maximal Matching M to be empty.

2️⃣ While an Augmenting Path p exists, remove the matching edges of p from M and add the not-matching edges of p to M.

3️⃣ Return M

### Implementation

C++ Program to implement Hopcroft-Karp Algorithm for Maximum Matching:-

```
#include<bits/stdc++.h>
using namespace std;
#define NIL 0
#define INF INT_MAX
class Bipartite_Graph
{
int n, m;
list<int> *adj;
int *pair_U, *pair_V, *dist;
public:
Bipartite_Graph(int m, int n);
void add_Edge(int u, int v);
bool bfs();
bool dfs(int u);
int hckalgo();
};
int Bipartite_Graph::hckalgo()
{
pair_U = new int[m+1];
pair_V = new int[n+1];
dist = new int[m+1];
for (int i=0; i<=m; i++)
pair_U[i] = NIL;
for (int j=0; j<=n; j++)
pair_V[j] = NIL;
int res = 0;
while (bfs())
{
for (int u=1; u<=m; u++)
if (pair_U[u]==NIL && dfs(u))
res++;
}
return res;
}
bool Bipartite_Graph::dfs(int u)
{
if (u != NIL)
{
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); i++)
{
int v = *i;
if (dist[pair_V[v]] == dist[u]+1)
{
if (dfs(pair_V[v]) == true)
{
pair_V[v] = u;
pair_U[u] = v;
return true;
}
}
}
dist[u] = INF;
return false;
}
return true;
}
bool Bipartite_Graph::bfs()
{
queue<int> q;
for (int u=1; u<=m; u++)
{
if (pair_U[u]==NIL)
{
dist[u] = 0;
q.push(u);
}
else dist[u] = INF;
}
dist[NIL] = INF;
while (!q.empty())
{
int u = q.front();
q.pop();
if (dist[u] < dist[NIL])
{
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); i++)
{
int v = *i;
if (dist[pair_V[v]] == INF)
{
dist[pair_V[v]] = dist[u] + 1;
q.push(pair_V[v]);
}
}
}
}
return (dist[NIL] != INF);
}
// Constructor
Bipartite_Graph::Bipartite_Graph(int m, int n)
{
this->m = m;
this->n = n;
adj = new list<int>[m+1];
}
void Bipartite_Graph::add_Edge(int u, int v)
{
adj[u].push_back(v);
}
// Driver Program
int main()
{
Bipartite_Graph g(4, 4);
g.add_Edge(1, 2);
g.add_Edge(1, 3);
g.add_Edge(2, 1);
g.add_Edge(3, 2);
g.add_Edge(4, 2);
g.add_Edge(4, 4);
cout << g.hckalgo();
return 0;
}
```

**Output:**

` 4`

#### Time Complexity

The time complexity of the Hopcroft-Karp Algorithm for maximum matching is O(√V x E), where E is the number of Edges and V is the number of vertices.

#### Space Complexity

The space complexity of the Hopcroft-Karp Algorithm is O(V) as we are using extra space for storing u and v.

Check out this problem - __Check If A String Is Palindrome__