Algorithm/Hopcroft_Karp.cpp at master · rituraj0/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include<vector>
#include<algorithm>
using namespace std;

class HCK
{
    int N,M;
    vector<int> matchL, matchR, distL, distR, Q;
    vector<vector<int> > adjList;
    int qf, qb;

    inline bool bfs()
    {
        fill(distL.begin(), distL.end(), -1);
        fill(distR.begin(), distR.end(), -1);
        qf = qb = 0;

        for(int i = 0; i < N; i++)
            if( matchL[i] == -1)
                distL[i] = 0, Q[qb++] = i;

        bool found = false;
        while( qf < qb)
        {
            int u = Q[qf++];
            for(int i = 0; i < adjList[u].size(); i++)
            {
                int v = adjList[u][i];
                if( distR[v] >= 0)	continue;		// Seen vertex
                    distR[v] = 1 + distL[u];
                if( matchR[v] == -1)	// Unmatched vertex, aug path exists. Don't push vertices anymore on queue
                    found  = true;
                else
                {
                    Q[qb++] = matchR[v];
                    distL[matchR[v]] = 1 + distR[v];
                }
            }
        }
        return found;
    }


    inline bool dfs(int u)
    {
        for(int i= 0; i < adjList[u].size(); i++)
        {
            int v = adjList[u][i];
            if( distR[v] == distL[u] + 1)			// u -> v is a forward edge
            {
                distR[v]  = -1;				        // Mark this vertex as seen.
                if( matchR[v] == -1 || dfs(matchR[v]) )
                {
                    matchL[u] = v;	matchR[v] = u;
                    distL[u] = -1;				    // 	Mark this vertex as seen.
                    return true;
                }
            }
        }

        distL[u] = -1;							    // Mark this vertex as seen.
        return false;
    }

    public:
    void init(int lsize, int rsize)
    {
       //using namespace std;
        N = lsize, M = rsize;
        matchL.clear(); matchL.resize(N);
        matchR.clear(); matchR.resize(M);
        distL.clear();  distL.resize(N);
        distR.clear();  distR.resize(M);
        Q.resize(N); qf = qb = 0;

        adjList.resize(N);
        for(int i = 0; i < N; i++)
            adjList[i].clear();
    }

    inline void addEdge(int l, int r)
    {
        adjList[l].push_back(r);
    }

    int maxMatching()
    {
        fill(matchL.begin(), matchL.end(), -1);
        fill(matchR.begin(), matchR.end(), -1);
        int match = 0;
        while(bfs())
        {
            for(int i = 0; i < N; i++)
                if( matchL[i] == -1 && dfs(i) ) match++;
        }
        return match;
    }
};


int main()
{
     //Sample usage
    HCK hck;

    // initialize with left and right partition sizes
    hck.init(10, 20);

    // Add some edges
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 20; j++)
            if( (i + j) & 1)
                hck.addEdge(i, j);

    int max_match = hck.maxMatching();
    cout << max_match << endl;
    return 0;
}