catalogue

1, What is a bipartite graph?

2, Dyeing method

3, Hungarian algorithm

summary

1, What is a bipartite graph?

Bipartite graph, also known as bipartite graph, is a kind of graph theory Special model . Let G=(V,E) be an undirected graph. If vertex v can be divided into two disjoint subsets (A,B), and the two vertices i and j associated with each edge (i, J) in the graph belong to these two different vertex sets (i in A,j in B), then graph G is called a bipartite graph.

That is, all points are divided into two sets, and all edges connect the points in different sets; There are no edges in each collection

If and only if there are no odd rings in Bipartite Graphs

2, Dyeing method

The coloring method is used to judge whether a graph is a bipartite graph; Since there are no odd rings in bipartite graphs, there is no contradiction in the coloring process;

For each vertex, if the color is determined, the color of all vertices of the whole graph can be determined; And the two vertices of each edge must have different colors.

Core idea: dfs judges whether there are contradictions in the subtree with the current node as the root

Template questions:

Link: https://www.acwing.com/problem/content/862/

/**
 * Coloring method: judge whether a graph is a bipartite graph
 *  dfs Every time a subtree rooted at the current node is dyed, as long as there is a contradiction, it is not a bipartite graph
 */ 
 
 #include <iostream>
 #include <cstdio>
 #include <cstring>
 
 using namespace std;
 const int N = 100010;
 int n, m;
 int e[N * 2], ne[N * 2], h[N], idx;
 int match[N]; // Record the number of stains
 
 void add(int a, int b) {
     e[idx] = b;
     ne[idx] = h[a];
     h[a] = idx ++;
 }
 
 bool dfs(int x, int color) {
     match[x] = color;
     
     for (int i = h[x]; i != -1; i = ne[i]) {
         int j = e[i];
         if (!match[j]) {
             if(!dfs(j, 3 - color)) return false;
         } else if (match[j] == color) return false;
     }
     
     return true;
 }
 
 int main()
 {
     memset(h, -1, sizeof h);
     cin >> n >> m;
     while (m --) {
         int a, b;
         cin >> a >> b;
         add(a, b); 
         add(b, a);
     }
     // Traverse the collection to see if there will be a contradiction
     bool flag = true;
     for (int i = 1; i <= n; i++) {
         if (!match[i]) {
             // dfs meaning: coloring the number of words with i as the root, where the color of vertex i is 1
             if (!dfs(i, 1)) {
                 flag = false;
                 break;
             } 
         }
     }

     if (flag) puts("Yes");
     else puts("No");
     return 0;
 }

3, Hungarian algorithm

Determine the maximum matching of bipartite graph. The worst time complexity O(n * m); But the reality is much smaller than this theory

Matching of bipartite graphs: given a bipartite graph {GG}, in a subgraph {mm} of {GG}, if any two edges in the edge set {E}{E} of MM} are not attached to the same vertex, then {mm} is a matching.

Maximum matching of bipartite graph: a group of matches with the largest number of edges in all matches is called the maximum matching of bipartite graph, and the number of edges is the maximum matching number.

Algorithm idea: the two sets in the bipartite graph are regarded as boys and girls for matching. Suppose that only the male set is traversed, and the first female is selected to match it; If the selected girl has been selected, try to change the boy who matches the girl to another candidate; Otherwise, you can only give up

Therefore, when constructing a graph, you only need to ensure the edges in one direction, that is, a directed graph

Template questions:

Link: https://www.acwing.com/problem/content/863/

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 510, M = 100010;
int e[M], ne[M], h[N], idx;
int match[N]; // Store matching boys
bool vis[N]; // The tag cannot select a girl repeatedly
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]) {
        int j = e[i];
        if (!vis[j]) {
            vis[j] = true;
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        } 
    }
    return false;
}


int main()
{
    memset(h, -1, sizeof h);
    int n1, n2, m;
    scanf("%d%d%d", &n1, &n2, &m);
    while (m --) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    // Ergodic boy set
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(vis, false, sizeof vis);
        if(find(i)) { // Find i matching points
            res ++;
        }
    }
    printf("%d\n", res);
    return 0;
}

summary

Just touch the bipartite graph and record the two algorithms learned