JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - New Recipes Solving Maximum Bipartite Matching Problem Revision History (35 edits)
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is a bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them have adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges in the bipartite graph. Alternating chain (in a bipartite graph, with respect to some matching) is a chain in which the edges alternately belong / not belong to the matching. The increasing chain (in a bipartite graph, with respect to a matching) is an alternating chain, whose initial and final vertices (as well as edges) do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that by doing this operation we will increase our matching by one, because length of increasing chain is always odd and because in this chain we had [k/2]+1 unmarked edges and [k/2] marked edges and after rematching we have [k/2] unmarked edges and [k/2]+1 marked edges in the chain.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will search increasing chains: we shall use dfs. We will call dfs only from vertices of graph’s left part. From left part it goes to right only using not marked edges, and from right to left only using marked edges. In our implementation dfs will be called only from left graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go through all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true, because it is last vertex of increasing chain. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Do not clear used marks after you find one path. Instead of it run a series of DFS-es over all vertices in a single phase. One such phase takes strictly O(V+E) time (graph full traversal) and can find more than one increasing path at once. Moreover, the first phase will behave precisely as greedy algorithm (which is also improvement). After running each phase you should clear used and run the next phase. Terminate when no path is found during one phase.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs_of_right, pairs_of_left;
	vector<bool> used;
 
 
	bool kuhn (int v) 
	{
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
		{
			int to = g[v][i]-n;
			if (pairs_of_right[to] == -1 || kuhn (pairs_of_right[to])) 
			{
				pairs_of_right[to] = v;
				pairs_of_left[v] = to;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs_of_right = vector<int> (k, -1);
		pairs_of_left = vector<int> (n, -1);
		//pairs_of_right[i] is a neighbor of vertex i from right part, on marked edge
		//pairs_of_left[i]  is a neighbor of vertex i from left part, on marked edge
		used = vector<bool> (n, false);
 
 
		bool path_found;
		do {
			fill(used.begin(), used.end(), false);
			path_found = false;
			//remember to start only from free vertices which are not visited yet
			for (int i = 0; i < n; ++i)
				if (pairs_of_left[i] < 0 && !used[i])
					path_found |= kuhn (i);
		} while (path_found);
 
 
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs_of_right[i] != -1)
				res.push_back(make_pair(pairs_of_right[i], i+n));
 
		return res;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is a bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them have adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges in the bipartite graph. Alternating chain (in a bipartite graph, with respect to some matching) is a chain in which the edges alternately belong / not belong to the matching. The increasing chain (in a bipartite graph, with respect to a matching) is an alternating chain, whose initial and final vertices (as well as edges) do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that by doing this operation we will increase our matching by one, because length of increasing chain is always odd and because in this chain we had [k/2]+1 unmarked edges and [k/2] marked edges and after rematching we have [k/2] unmarked edges and [k/2]+1 marked edges.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will search increasing chains: we shall use dfs. We will call dfs only from vertices of graph’s left part. From left part it goes to right only using not marked edges, and from right to left only using marked edges. In our implementation dfs will be called only from left graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go through all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true, because it is last vertex of increasing chain. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Do not clear used marks after you find one path. Instead of it run a series of DFS-es over all vertices in a single phase. One such phase takes strictly O(V+E) time (graph full traversal) and can find more than one increasing path at once. Moreover, the first phase will behave precisely as greedy algorithm (which is also improvement). After running each phase you should clear used and run the next phase. Terminate when no path is found during one phase.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs_of_right, pairs_of_left;
	vector<bool> used;
 
 
	bool kuhn (int v) 
	{
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
		{
			int to = g[v][i]-n;
			if (pairs_of_right[to] == -1 || kuhn (pairs_of_right[to])) 
			{
				pairs_of_right[to] = v;
				pairs_of_left[v] = to;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs_of_right = vector<int> (k, -1);
		pairs_of_left = vector<int> (n, -1);
		//pairs_of_right[i] is a neighbor of vertex i from right part, on marked edge
		//pairs_of_left[i]  is a neighbor of vertex i from left part, on marked edge
		used = vector<bool> (n, false);
 
 
		bool path_found;
		do {
			fill(used.begin(), used.end(), false);
			path_found = false;
			//remember to start only from free vertices which are not visited yet
			for (int i = 0; i < n; ++i)
				if (pairs_of_left[i] < 0 && !used[i])
					path_found |= kuhn (i);
		} while (path_found);
 
 
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs_of_right[i] != -1)
				res.push_back(make_pair(pairs_of_right[i], i+n));
 
		return res;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is a bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them have adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges in the bipartite graph. Alternating chain (in a bipartite graph, with respect to some matching) is a chain in which the edges alternately belong / not belong to the matching. The increasing chain (in a bipartite graph, with respect to a matching) is an alternating chain, whose initial and final vertices (as well as edges) do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that by doing this operation we will increase our matching by one because length of increasing chain is always odd and because in this chain we had [k/2]+1 unmarked edges and [k/2] marked edges.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will search increasing chains: we shall use dfs. We will call dfs only from vertices of graph’s left part. From left part it goes to right only using not marked edges, and from right to left only using marked edges. In our implementation dfs will be called only from left graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go through all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true, because it is last vertex of increasing chain. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Do not clear used marks after you find one path. Instead of it run a series of DFS-es over all vertices in a single phase. One such phase takes strictly O(V+E) time (graph full traversal) and can find more than one increasing path at once. Moreover, the first phase will behave precisely as greedy algorithm (which is also improvement). After running each phase you should clear used and run the next phase. Terminate when no path is found during one phase.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs_of_right, pairs_of_left;
	vector<bool> used;
 
 
	bool kuhn (int v) 
	{
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
		{
			int to = g[v][i]-n;
			if (pairs_of_right[to] == -1 || kuhn (pairs_of_right[to])) 
			{
				pairs_of_right[to] = v;
				pairs_of_left[v] = to;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs_of_right = vector<int> (k, -1);
		pairs_of_left = vector<int> (n, -1);
		//pairs_of_right[i] is a neighbor of vertex i from right part, on marked edge
		//pairs_of_left[i]  is a neighbor of vertex i from left part, on marked edge
		used = vector<bool> (n, false);
 
 
		bool path_found;
		do {
			fill(used.begin(), used.end(), false);
			path_found = false;
			//remember to start only from free vertices which are not visited yet
			for (int i = 0; i < n; ++i)
				if (pairs_of_left[i] < 0 && !used[i])
					path_found |= kuhn (i);
		} while (path_found);
 
 
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs_of_right[i] != -1)
				res.push_back(make_pair(pairs_of_right[i], i+n));
 
		return res;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implementation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Do not clear used marks after you find one path. Instead of it run a series of DFS-es over all vertices in a single phase. One such phase takes strictly O(V+E) time (graph full traversal) and can find more than one increasing path at once. Moreover, the first phase will behave precisely as greedy algorithm, so it supersedes you greedy improvement. After running each phase you should clear used marks and run the next phase. Terminate when no path is found during one phase.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs_of_right, pairs_of_left;
	vector<bool> used;
 
 
	bool kuhn (int v) 
	{
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
		{
			int to = g[v][i]-n;
			if (pairs_of_right[to] == -1 || kuhn (pairs_of_right[to])) 
			{
				pairs_of_right[to] = v;
				pairs_of_left[v] = to;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs_of_right = vector<int> (k, -1);
		pairs_of_left = vector<int> (n, -1);
		//pairs_of_right[i] is a neighbor of vertex i from right part, on marked edge
		//pairs_of_left[i]  is a neighbor of vertex i from left part, on marked edge
		used = vector<bool> (n, false);
 
 
		bool path_found;
		do {
			fill(used.begin(), used.end(), false);
			path_found = false;
			//remember to start only from free vertices which are not visited yet
			for (int i = 0; i < n; ++i)
				if (pairs_of_left[i] < 0 && !used[i])
					path_found |= kuhn (i);
		} while (path_found);
 
 
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs_of_right[i] != -1)
				res.push_back(make_pair(pairs_of_right[i], i+n));
 
		return res;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implementation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Do not clear used marks after you find one path. Instead of it run a series of DFS-es over all vertices in a single phase. One such phase takes strictly O(V+E) time (graph full traversal) and can find more than one increasing path at once. Moreover, the first phase will behave precisely as greedy algorithm, so it supersedes you greedy improvement. After running each phase you should clear used marks and run the next phase. Terminate when no path is found during one phase.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v)
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) 
                                {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i)
                {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implementation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(pairs[q])) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v)
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) 
                                {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i)
                {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implementation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) 
{
        if (used[v]) return false;
        used[v] = true;
 
        for(vertex q adjacent to v) 
        {
                if((q has no pair) or kuhn(q)) 
                {
                        pairs[q] = v;
                        return true;
                }   
        }
}
find_max_matching 
{
        for(vertex v = {1,..,n}) 
        {
                used = {0};
                kuhn(v);
        }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) 
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) 
                {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v)
        {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) 
                {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) 
                        {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) 
        {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) 
                                {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i)
                {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

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][n+v[i][j]] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

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][n+v[i][j]] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

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][n+v[i][j]] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left patr and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left part and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

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 g[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][n+v[i][j]] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left par and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class KuhnImplementation
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i, where i is from left par and g[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
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

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 par and g[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][n+v[i][j]] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i from right part, on marked edge
		used = vector<bool> (n, false);
		for (int i = 0; i < n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,...,n+k} (from left part) and
		//      v[i].second = {1,...,n+k} (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++)
			g[v[i].first][n+v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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][n+j] = 1 if there is edge between i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][n+v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = 0; i < k; i++)
			g[n+i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent not marked edges to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our implemantation dfs will be called only from first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to it.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices (n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved in two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked (first edge is not marked by definition – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So the main idea of the algorithm is to search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs (depth first search) or bfs (breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO has no adjacent marked edges, dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation (C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn(q)) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Pseudocode:
bool kuhn(vertex v) {
  if (used[v]) return false;
  used[v] = true;
 
  for(vertex q adjacent to v) {
    if((q has no pair) or kuhn[q]) {
      pairs[q] = v;
      return true;
    }   
  }
}
find_max_matching {
  for(vertex v = {1,..,n}) {
    used = {0};
    kuhn(v);
  }
}

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

SOLUTION
First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices(n vertices in left part and k = N-n vertices in right part of graph) and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

PROBLEM
In this article we shall speak about Solving Maximum Bipartite Matching Problem. There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other. This problem can be easily solved by two ways.

First way: Kuhn’s algorithm.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
NAME
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
<b color = red>Name
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};

Solving maximum bipartite problem can be useful to solve problems using Hungarian algorithm(http://www.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709), minimum vertex cover, etc.
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.

Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.



<img>

</img>


Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):


#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};

Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.






Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):


#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k) {
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
			for(int j = 0; j < g[i].size(); j++)
				if(pairs[g[i][j]-n] == -1) {
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};

Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k) {
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.






Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.


So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):


#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < g[i].size(); j++)
			{
				if(pairs[g[i][j]-n] == -1)
				{
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
			}
		}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};

Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k)	
	{
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.






Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.

So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):


#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < g[i].size(); j++)
			{
				if(pairs[g[i][j]-n] == -1)
				{
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
			}
		}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};

Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k)	
	{
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.






Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.

So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):


#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex I on marked edge
		used = vector<bool> (n, false);
		for (int i=0; i<n; ++i) {
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};


Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.
#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
public:
	int n, k;
	vector < vector<int> > g;
	vector<int> pairs;
	vector<bool> used;
 
 
	bool kuhn (int v) {
		if (used[v])  return false;
		used[v] = true;
		for (int i = 0; i < g[v].size(); ++i) {
			int to = g[v][i]-n;
			if (pairs[to] == -1 || kuhn (pairs[to])) {
				pairs [to] = v;
				return true;
			}
		}
		return false;
	}
 
	vector<pair<int, int> > find_max_matching(vector<vector<int> > &_g, int _n, int _k)
	{
		g = _g;
		//g[i] is a list of adjacent vertices to vertex i
		n = _n;
		//n is number of vertices in left part of graph
		k = _k;
		//k is number of vertices in right part of graph
 
		pairs = vector<int> (k, -1);
		//pairs[i] is a neighbor of vertex i on marked edge
		used = vector<bool> (n, false);		
		vector<bool> used1(n);
 
 
		
 
 
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < g[i].size(); j++)
			{
				if(pairs[g[i][j]-n] == -1)
				{
					pairs[g[i][j]-n] = i;
					used1[i] = true;
					break;
				}
			}
		}
 
 
 
		for (int i=0; i<n; ++i) {
			if(used1[i]) continue;
			fill(used.begin(), used.end(), false);
			kuhn (i);
		}
	
		vector<pair<int, int> > res;
		for(int i = 0; i < k; i++)
			if(pairs[i] != -1)
				res.push_back(make_pair(pairs[i], i+n));
 
		return res;
 
	}
};

Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;
 
class MyClass
{
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<pair<int, int> > &v, int _n, int _k)	
	{
		//v[i] is edge between vertex 
		//	v[i].first  = {1,..,n} (from left part) and
		//      v[i].second = {1,..,k} (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 i-th vertex from left part 
		//            			    and j-th from right part
		for(int i = 0; i < v.size(); i++)
			g[v[i].first][v[i].second] = 1;
		int A = n+k;
		int B = n+k+1; 
		for(int i = 0; i < n; i++)
			g[A][i] = 1;
		for(int i = n; i < n+k; i++)
			g[i][B] = 1;
 
		vector<vector<int> > _g(g);
 
		used = vector<bool> (n+k+2, false);
		while(find_path(A, B))
			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;
 
	}
};
Solving Maximum Bipartite Matching Problem
Solving Maximum Bipartite Matching Problem

In this article we shall speak about Solving Maximum Bipartite Matching Problem. This problem can be easily solved by two ways.


First way: Kuhn’s algorithm.

There is bipartite graph containing N vertices and M edges. We are to find maximum bipartite matching, i.e. mark maximum number of edges, so that no one of them had adjacent vertices with each other.






Chain with length k is a simple path (i.e. it contains no repeated vertices or edges) that has k edges. Alternating chain (in a bipartite graph, with respect to a matching) is a chain in which the edges alternately belong / not belong to a matching. The increasing chain (in a bipartite graph, with respect to a matching) is a chain, whose initial and final vertices do not belong to matching.

Berja’s theorem:
Matching is maximal if and only if there are no increasing chains with respect to him.

So, let’s notice that if we find an increasing chain, we can increase our matching by one. We will go along this increasing chain and mark edges which are not marked and unmark edges that were marked(first edge isn’t marked (by definition) – we will mark it, second is marked, so we will unmark it and so on). It is obvious that doing this operation we will increase our matching by one because length of increasing chain is always odd.

So that is the algorithm: we will search increasing chains while we can and increase matching.

Well, new problem is how to find increasing chains. Kuhn’s algorithm is based on dfs(depth first search) or bfs(breadth first search) algorithm.

Complexity of searching an increasing chain is O(N+M) and maximum number of them is N/2, overall asymptotic is O(N*N + N*M) = O(NM)

Let’s see how we will look for increasing chains: here we shall use dfs. Our dfs will be called only from vertices of graph’s left part. From first part it goes to second only using not marked edges, and from second to first only using marked edges. In our realization dfs will be only in first graph’s vertices and will return bool – true if it found chain and false if not. From current vertex algorithm will go on all adjacent edges which are not marked to vertex from right part called TO. If TO hasn’t adjacent marked edges dfs will return true. If it has, we will call dfs from TO’s neighbor on marked edge and return true if it returned true.

Implementation(C++):



#include<vector>
#include<utility>
using namespace std;

class MyClass
{
public:
int n, k;
vector < vector<int> > g;
vector<int> pairs;
vector<bool> used;


bool kuhn (int v) {
if (used[v]) return false;
used[v] = true;
for (int i = 0; i < g[v].size(); ++i) {
int to = g[v][i]-n;
if (pairs[to] == -1 || kuhn (pairs[to])) {
pairs [to] = v;
return true;
}
}
return false;
}

vector<pair><int, int> > find_max_matching(vector<vector><int> > &_g, int _n, int _k)
{
g = _g;
//g[i] is a list of adjacent vertices to vertex i
n = _n;
//n is number of vertices in left part of graph
k = _k;
//k is number of vertices in right part of graph

pairs = vector<int> (k, -1);
//pairs[i] is a neighbor of vertex I on marked edge
used = vector<bool> (n, false);
for (int i=0; i<n; ++i) {
fill(used.begin(), used.end(), false);
kuhn (i);
}

vector><pair><int, int> > res;
for(int i = 0; i < k; i++)
if(pairs[i] != -1)
res.push_back(make_pair(pairs[i], i+n));

return res;

}
};

Improved implementation:

Let’s modify algorithm in next way. Before doing main cycle we will find any matching using maybe greedy algorithm. After that Kuhn’s algorithm will work a couple times faster. Iterating over edges we will add edge to matching if it can be added. But we will have to modify main cycle too.

#include<vector>
#include<utility>
using namespace std;

class MyClass
{
public:
int n, k;
vector < vector<int> > g;
vector<int> pairs;
vector<bool> used;


bool kuhn (int v) {
if (used[v]) return false;
used[v] = true;
for (int i = 0; i < g[v].size(); ++i) {
int to = g[v][i]-n;
if (pairs[to] == -1 || kuhn (pairs[to])) {
pairs [to] = v;
return true;
}
}
return false;
}

vector<pair><int, int> > find_max_matching(vector<vector><int> > &_g, int _n, int _k)
{
g = _g;
//g[i] is a list of adjacent vertices to vertex i
n = _n;
//n is number of vertices in left part of graph
k = _k;
//k is number of vertices in right part of graph

pairs = vector<int> (k, -1);
//pairs[i] is a neighbor of vertex i on marked edge
used = vector<bool> (n, false);
vector<bool> used1(n);





for(int i = 0; i < n; i++)
{
for(int j = 0; j < g[i].size(); j++)
{
if(pairs[g[i][j]-n] == -1)
{
pairs[g[i][j]-n] = i;
used1[i] = true;
break;
}
}
}



for (int i=0; i<n; ++i) {
if(used1[i]) continue;
fill(used.begin(), used.end(), false);
kuhn (i);
}

vector><pair><int, int> > res;
for(int i = 0; i < k; i++)
if(pairs[i] != -1)
res.push_back(make_pair(pairs[i], i+n));

return res;

}
};
Second way: Maximum flow algorithm.

Solving this problem using maximum flow algorithm is obvious. We will create two new vertices: A and B. We will create edges from A to all vertices of left part of graph and we will create edges from all vertices of right part of graph to B. All edges capacity will be equal to 1. After that we need to find maximum flow from A to B.
All used edges between left and right parts are maximum matching.

Implementation:

#include<vector>
#include<utility>
using namespace std;

class MyClass
{
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<pair><int, int> > &v, int _n, int _k)
{
//v[i] is edge between vertex
// v[i].first = {1,..,n} (from left part) and
// v[i].second = {1,..,k} (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 i-th vertex from left part
// and j-th from right part
for(int i = 0; i < v.size(); i++)
g[v[i].first][v[i].second] = 1;
int A = n+k;
int B = n+k+1;
for(int i = 0; i < n; i++)
g[A][i] = 1;
for(int i = n; i < n+k; i++)
g[i][B] = 1;

vector<vector><int> > _g(g);

used = vector<bool> (n+k+2, false);
while(find_path(A, B))
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;

}
};