The concept of bipartite graph: bipartite graph, also called bipartite graph, is a special model in graph theory. Let G=(V,E) be an undirected graph. If vertex V is divisible into two disjoint subsets (A,B) and the two vertices I and J associated with each edge (I,j) belong to these two different sets of vertices (I in A,j in B), then graph G is called A bisection graph.
Match: In graph theory, a match is a set of edges in which any two edges have no common vertices.
Maximum match: The match with the largest number of matching edges among all matches in a graph is called the maximum match of the graph.
Alternate path: starting from an unmatched point, through the unmatched edge, the matched edge, the unmatched edge… The path formed is called an alternate path.
Augmented path: An alternate path starting from an unmatched point. If it follows another unmatched point, the alternate path is called augmented path.
An important feature of the augmented path is that the number of unmatched edges is one more than the number of matched edges. In this way, the number of matched edges can be increased by one by exchanging the identity of the unmatched and matched edges. Therefore, the augmented path is always searched to increase the number of matches until no enhanced path is found.
Code Implementation (Dfs) :
Struct Edge {int from; int to; }; vector <int> G[max]; Int matchingNode [Max]; int check[max]; int Dfs(int u) { vector <int>::iterator it;for(it=G[u].begin(); it! =G[u].end(); it++) { int v=*it;if(! Check [v]) {check[v]=1;if(matchingnode [v] = = 1 | | Dfs (matchingnode [v])) / / is {matching point matching [v] = u; matching[u]=v;return1; }}}return 0;
}
int hungarian ()
{
int _count;
memset(matchingnode,-1,sizeof(matchingnode));
for(int i=0; i<max; i++) {if(matchingnode[i]==-1)
{
memset(check,0,sizeof(check));
if(Dfs(i)) _count++; }}return _count;
}Copy the code
Use the cloud habitat community APP, comfortable ~
The original link