
Second way: Maximum flow algorithm.
Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: S and T. We will create edges from S to all vertices of left part of graph and we will create edges from all vertices of right part of graph to T. All edges capacity will be equal to 1. After that we need to find maximum flow from S to T. All used edges between left and right parts are maximum matching. It is obvious why it works. It is easier to understand, especially if you understand and know how to code max flow algorithm.
Implementation:
#include<vector>
#include<utility>
using namespace std;
class MaxFlowImplementation
{
public:
vector<vector<int> > g;
vector<bool> used;
int n, k;
bool find_path(int a, int b)
{
if(a == b) return true;
if(used[a]) return false;
used[a] = true;
for(int i = 0; i < n+k+2; i++)
if(g[a][i] > 0 && find_path(i, b))
{
g[a][i];
g[i][a]++;
return true;
}
return false;
}
vector<pair<int, int> > find_max_matching(vector<vector<int> > &v, int _n, int _k)
{
//v[i] is a list of adjacent vertices to vertex i, where i is from left part and v[i][j] is from right part
n = _n;
//n is number of vertices in left part of graph
k = _k;
//k is number of vertices in right part of graph
g = vector<vector<int> >(n+k+2, vector<int>(n+k+2));
//g[i][j] = 1 if there is edge between vertex i from left part
// and vertex j from right part
for(int i = 0; i < v.size(); i++)
for(int j = 0; j < v[i].size(); j++)
g[i][v[i][j]] = 1;
int S = n+k;
int T = n+k+1;
for(int i = 0; i < n; i++)
g[S][i] = 1;
for(int i = 0; i < k; i++)
g[n+i][T] = 1;
vector<vector<int> > _g(g);
used = vector<bool> (n+k+2, false);
while(find_path(S, T))
fill(used.begin(), used.end(), false);
vector<pair<int, int> > res;
for(int i = 0; i < n; i++)
for(int j = n; j < n+k; j++)
if(g[i][j] < _g[i][j])
res.push_back(make_pair(i, j));
return res;
}
};
DISCUSSION Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm, minimum vertex cover, etc. To tell the truth, while max  flow implementation is easier to understand and implement, Kuhn algorithm is more effective, especially improved implementation.
Good example of using this algorithm in solving Topcoder Problem is PythTriplets Problem. We have numbers. Some pairs of these numbers are good. For example, we have {a, b, c, d}. Let good pairs be: (a,b) (b,c) (c,d). We need to select maximum amount of pairs so that no number to be in different pairs. Here they are (a,b) and (c,d).
Of course first you need to do is build a graph. Each vertex is a number. After creating edges between vertices (create edge between a and b if gcd(a, b) = 1 and a^{2} + b^{2} = (some integer)^{2}). The trick is that it is a bipartite graph. How to build a bipartite graph? There are two ways here.
First way is to notice that if we place all even numbers to left part and all odd numbers to right part then we will get a bipartite graph. How to prove it? First no edge can be between even numbers because gcd(2*x, 2*y) >= 2. Second no edge can be between odd numbers because (2*x+1)^2 + (2*y+1)^2 = = 4*x*x + 4*x + 1 + 4*y*y + 4*y + 1 = = 4*x*x + 4*x + 4*y*y + 4*y + 2 = = 2*(2*x*x + 2*x + 2*y*y + 2*y + 1) = = 2 * z; where z is odd number and we can't divide ((2*x+1)^2 + (2*y+1)^2) twice, so there is no integer square root of ((2*x+1)^2 + (2*y+1)^2).
Second way is to build a bipartite graph using algorithm. We will go through vertices and call dfs() from unused vertices placing them to left part, its neighbors to right part and so on.
After that we just find maximum matching and return it's size:
class PythTriplets
{
public:
int gcd(int a, int b)
{
return b?gcd(b, a%b):a;
}
bool edge(int a, int b)//is there an edge between a and b?
{
long long _a = a, _b = b, n = _a*_a + _b*_b;
long long sqr = (long long)(sqrt((double)(n))+1e9);
if(sqr*sqr != n) return false;
return gcd(a, b) == 1;
}
int findMax(vector <string> stick)
{
string s;
for(int i = 0; i < stick.size(); i++)
s += stick[i];
vector<int> v;
istringstream is(s);
int a;
while(is >> a)
v.push_back(a);
vector<int> nums;//even numbers and then odd numbers(first n numbers are even, the rest are odd)
for(int i = 0; i < v.size(); i++)
if(v[i]%2 == 0)
nums.push_back(v[i]);
int n = nums.size(), k = v.size()  n;
for(int i = 0; i < v.size(); i++)
if(v[i]%2 == 1)
nums.push_back(v[i]);
vector<vector<int> > g(nums.size());
for(int i = 0; i < v.size(); i++)
for(int j = i+1; j < v.size(); j++)
if(edge(nums[i], nums[j]))
g[i].push_back(j);
//if you use Kuhn algorithm
KuhnImplementation obj;
// or if you use max flow algorithm
//MaxFlowImplementation obj
return obj.find_max_matching(g, n, k).size();
}
};
Another good example of using this algorithm is problem RookAttack, here we have chessboard with n rows and k columns and we have to place maximum number of rooks there so that no of them will attack each other. But we also have some broken cells, where we can't place rooks. So we create a bipartite graph, where rows are vertices from left part of graph and columns are vertices from right part of graph and we create an edge between row and column if this cell is not broken. After that we just find maximum bipartite matching and return its size. It works because if we use cell board[i][j] then we can't use cells on the same row or column and the same is right for edge in Maximum Bipartite Matching Problem: if we use some edge ab, we can't use edges which has any vertices of a or b.
Implementation:
class RookAttack
{
public:
int howMany(int n, int k, vector <string> cuts)
{
vector<vector<int> > g(n);
vector<vector<bool> > _g(n, vector<bool> (k, true));
for(int i = 0; i < cuts.size(); i++)
{
istringstream is(cuts[i]);
int a, b;
char c;
while(is >> a >> b)
{
_g[a][b] = false;
is >> c;
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
if(_g[i][j])
g[i].push_back(j+n);
//if you use Kuhn algorithm
KuhnImplementation obj;
// or if you use max flow algorithm
//MaxFlowImplementation obj
return obj.find_max_matching(g, n, k).size();
}
};
