Hopcroft Karp Algorithm for Maximum Matching | Implementatio

/**
 * Author                      : Dipu Kumar Mohanto (Dip)
 *                               CSE, BRUR.
 *                               Batch - 6
 *
 * Problem                     : Hopcroft Karp Algorithm for Maximum Matching | Implementation
 * Algorithm                   : Hopcroft Karp Algorithm for Maximum Matching
 * Complexity                  : O(sqrt(V) * E)
 * Category                    : Graph Theory, Bipartite Maximum Matching
 *
 * Difficulty                  :
 *
 * Source                      : GeeksForGeeks
 *
 * Verdict                     : OK
 *
 * Date                        :
 * E-mail                      : dipukumarmohanto1@gmail.com
**/


#include <bits/stdc++.h>

using namespace std;

#define VI                  vector <int>
#define pb                  push_back

#define inf                 1 << 28
#define NILL                0


const int mx = 1e6+6;


int m;             // no. of element's in left side
int n;             // no. of element's in right side


VI G[mx];

int pairU[mx];     // pairU[u] stores pair of u in matching where u
                   // is a vertex on left side of Bipartite Graph.
                   // If u doesn't have any pair, then pairU[u] is NILL

int pairV[mx];     // pairV[v] stores pair of v in matching. If v
                   // doesn't have any pair, then pairU[v] is NILL

int dist[mx];      // dist[u] stores distance of left side vertices
                   // dist[u] is one more than dist[u'] if u is next
                   // to u'in augmenting path









bool bfs()         // return's true if there is an augmenting
{                  // path, else returns false
    queue <int> PQ;

    // First layer of vertices (set distance as 0)
    for (int u=1; u<=m; u++)
    {
        // if there is a free vertex, add it to queue
        if (pairU[u] == NILL)
        {
            // u is not matched
            dist[u] = NILL;

            PQ.push(u);
        }

        // Else set distance as infinite so that this
        // vertex is considered next time
        else
            dist[u] = inf;
    }
    // Initialize distance to NILL as infinite
    dist[NILL] = inf;

    // Q is going to contain vertex of left side only
    while (!PQ.empty())
    {
        // Dequeue a vertex
        int u = PQ.front();
        PQ.pop();

        // If this vertex is not NILL and can provide a shorter path
        if (u != NILL && dist[u] < dist[NILL])
        {
            for (auto v : G[u])
            {
                // If pair of v is not considered so far
                // (v, pairV[V]) is not yet explored edge.
                if (dist[pairV[v]] == inf)
                {
                    dist[pairV[v]] = dist[u] + 1;

                    PQ.push(pairV[v]);
                }
            }
        }
    }
    // If we could come back to NIL using alternating path of distinct
    // vertices then there is an augmenting path
    if (dist[NILL] != inf)
        return true;

    else
        return false;
}







// Returns true if there is an augmenting path beginning with free vertex u
bool dfs(int u)
{
    if (u != NILL)
    {
        for (auto v : G[u])
        {
            // Follow the distances set by BFS
            if (dist[pairV[v]] == dist[u] + 1)
            {
                // If dfs for pair of v also returns
                // true
                if (dfs(pairV[v]))
                {
                    pairU[u] = v;
                    pairV[v] = u;

                    return true;
                }
            }
        }
        // If there is no augmenting path beginning with u.
        dist[u] = inf;
        return false;
    }
    return true;
}


int hopcropt_carp()
{
    int max_match = 0;

    // Keep updating the result while there is an
    // augmenting path
    while (bfs())
    {
        // Find a free vertex
        for (int u=1; u<=m; u++)
        {
            // If current vertex is free and there is
            // an augmenting path from current vertex
            if (pairU[u] == NILL && dfs(u))
            {
                max_match++;
            }
        }
    }
    return max_match;
}









int main()
{
    //freopen("in.txt", "r", stdin);

    int tEdge;
    cin >> m >> n >> tEdge;

    for (int e=1; e<=tEdge; e++)
    {
        int u, v;
        cin >> u >> v;

        G[u].pb(v);
        G[v].pb(u);
    }
    cout << "Size of matching is : " << hopcropt_carp() << endl;

    cout << "\n\tMatch pairs\nLeft Side ------- Right Side" << endl;

    for (int u=1; u<=m; u++)
    {
        // for directed pair
        //cout << "    " << u << "    -------    " << pairU[u] << endl;

        // for undirected pair
        cout << "    " << u << "    -------    " << pairV[u] << endl;
    }
}

/*******    Input Output     **********************/
4 4 6
1 2
1 3
2 1
3 2
4 2
4 4

Size of matching is : 4
Match pairs
Left Side ------- Right Side
    1    -------    3
    2    -------    1
    3    -------    2
    4    -------    4
/************************************************/