All the topics in this series are the content of the Acwing class. Posting a blog is not only for learning and summarizing, deepening your own impression, but also for not lamenting wasted time when you look back in the future. Therefore, if there are mistakes, everyone is welcome to point out the mistakes , I will seriously correct it. At the same time, I also hope that the article can give you something to share with you!

Today, let’s learn about bipartite graphs and their maximum matching. A bipartite graph means that the points in a graph are divided into two point sets, and there are no edges connecting the points inside the point set. They are only connected to points in another point set. A graph that has edges such that it can be divided into two parts that are internally unrelated is called a bipartite graph/bipartite graph.
The definition of a bipartite graph: A graph containing an odd number of cycles must not be a bipartite graph, and its converse proposition is that a bipartite graph must be a graph without an odd number of cycles.
A complete bipartite graph means that every point of a set has an edge with every point of another set. Such a graph is called a complete bipartite graph. So how to judge whether a graph is a bipartite graph? We can use the coloring method to judge the bipartite graph.

Coloring method to judge bipartite graph

Given an undirected graph with n vertices and m edges, multiple edges and self-loops may exist in the graph.

Please determine whether this graph is bipartite.

input format
The first line contains two integers n and m.

Next m lines, each line contains two integers u and v, indicating that there is an edge between point u and point v.

output format
If the given graph is bipartite, output Yes, otherwise output No.

data range
1≤n,m≤105
Input sample:

4 4
1 3
1 4
2 3
2 4

Sample output:

Yes

Algorithm principle

It should be noted that the bipartite graph is not necessarily a connected graph, so it is necessary to judge whether each point needs to be dyed, and dye all the connected blocks where this point is located.
Algorithm steps:
1.

Code

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5+10,M = 2e5+10;	// Undirected graph
int e[M],ne[M],h[N],idx;	// adjacency list graph
int color[N];	// Colors 1 and 2

void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool dfs(int u,int c){	// From the color of one point, the color of all other points can be judged
	color[u] = c;
	
	for(int i=h[u] ; i != -1 ; i = ne[i]){	// Iterate over all points connected to u
		int j = e[i];
		if(!color[j]){	// For points that are not colored
			if(!dfs(j,3-c))	return false;	// If there is an odd number of rings (a conflict occurs), it means that it cannot be dyed, and returns false
		}
		else if(color[j] == c)	return false;	// If the color of j is the same as that of yvu, there is a conflict (j's color should be 2 but it is 1)
	}
	return true;
}

int main(void){
	int n,m;
	cin >> n >> m;
	memset(h,-1,sizeof h);
	
	
	while(m--){
		int a,b;
		cin >> a >> b ;
		add(a,b);
		add(b,a);
	}
	
	bool flag = true;	// The flag is expressed as ture is a bipartite graph, and false is not a bipartite graph
	for(int i=1; i <= n ; ++i){	// Traverse all points from 1 to n
		if(!color[i]){	// Color the connected blocks where each point is located, and the dyed ones do not need to be dyed
			if(!dfs(i,1)){	// If there is an odd ring coloring conflict, it means that it is not a bipartite graph
				flag = false;
				break;
			}
		}
	}
	
	if(flag){
		puts("Yes");
	}
	else {
		puts("No");
	}
}

The entire basic graph theory finally only leaves the maximum matching of the bipartite graph, which is the Hungarian algorithm. When the time complexity is good, it is \(O(m)\), and when the time complexity is worst, it is \(O(mn)\). Due to the general example of y and the matching characteristics of the Hungarian algorithm, I call him the Yuelao algorithm when the time complexity is the best, the Tauren algorithm when the time complexity is medium, and the Tim dog algorithm when the time complexity is the worst. The content of the entire algorithm is the most interesting here.

Maximum matching of bipartite graphs

Given a bipartite graph, where the left half contains n1 points (numbered 1∼n1), and the right half contains n2 points (numbered 1∼n2), the bipartite graph contains a total of m edges.

The data guarantees that no two endpoints of any edge can be in the same part.

Please find the maximum matching number of the bipartite graph.

Bipartite graph matching: Given a bipartite graph G, in a subgraph M of G, if any two edges in M's edge set {E} do not attach to the same vertex, then M is said to be a matching.

The maximum matching of the bipartite graph: the group of matches that contains the most edges among all the matches is called the maximum matching of the bipartite graph, and the number of edges is the maximum number of matches.

input format
The first line contains three integers n1, n2 and m.

Next m lines, each line contains two integers u and v, indicating that there is an edge between point u in the left half of the point set and point v in the right half of the point set.

output format
Output an integer representing the maximum number of matches in the bipartite graph.

data range
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105
Input sample:

2 2 4
1 1
1 2
2 1
2 2

Sample output:

2

Algorithm principle

Let me first introduce what the maximum matching is here. The matching here refers to that each pair of points (belonging to two point sets respectively) can only match one side, and cannot match all sides at the same time. The maximum matching refers to requiring one of the sub-points Set best every point can be successfully matched.
If it is in If You Are the One, the match can be regarded as a successful hand in hand, the maximum match is to let us grow old in the same month, as many contestants as possible can successfully hold hands with the person they like, and the Hungarian algorithm is to use no more than \(O(mn)\) Let as many points as possible in one of the point sets be successfully matched within the time.
Note that the title has given us two bipartite graphs, we need to use the adjacency list to store them, connect a directed edge from the points in the left collection to the right collection, and need a match array to represent the matching of each point in the right collection Who is the person, this is to access the point on the left from the collection on the right, then accessing the collection on the right from the collection on the left can directly use the side to access, and there is an st indicating whether the girl on the right is holding hands successfully.

Code

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 510,M = 100010;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];


void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool find(int x){
	for(int i=h[x] ; i != -1; i = ne[i]){	// Find every girl on the right who has a good impression for x to hold hands
		int j = e[i];
		if(!st[j])	// girl j never held hands
		{
			st[j] = true;	// The girl was held by x
			if(match[j] == 0 || find(match[j])){	// If this girl is not successfully held by the previous contestants or is dumped by the previous contestants with this evil girl
				match[j] = x;	// Then this girl will find x to hold hands
				return true;	// x holding hands successfully
			}
		}
	}
	return false;	// If you can't find it without holding hands, it means you can't find it.
}

int main(void){
	cin >> n1 >> n2 >> m;
	memset(h,-1,sizeof h);
	
	while(m--){
		int a,b;
		cin >> a >> b ;
		add(a,b);		
	}	
	
	int res = 0;
	for(int i=1; i <= n1 ; ++i){
		memset(st,false,sizeof st);	// Every contestant has to try to lick from the head first, if it is not initialized to 0, then the following contestants will directly give up the chance to become a tauren
		if(find(i))	res++;	
	}
	
	cout << res;
	return 0;	
	
}