二分圖介紹

https://oi-wiki.org/graph/bi-graph/

二分圖是圖論中的一個(gè)概念，它的所有節(jié)點(diǎn)可以被分為兩個(gè)獨(dú)立的集合，每個(gè)邊的兩個(gè)端點(diǎn)分別來自這兩個(gè)不同的集合。
換句話說，二分圖中不存在連接同一集合內(nèi)兩個(gè)節(jié)點(diǎn)的邊。

染色法判定二分圖

如何判斷一個(gè)圖是二分圖？
當(dāng)且僅當(dāng)圖中不含奇數(shù)環(huán)。（奇數(shù)環(huán)指的是環(huán)中邊的個(gè)數(shù)是奇數(shù)）（因?yàn)槊恳粭l邊都是從一個(gè)集合走到另一個(gè)集合，只有走偶數(shù)次才有可能回到同一個(gè)集合。）

染色：相鄰的節(jié)點(diǎn)的顏色不一樣。

因?yàn)闆]有奇數(shù)環(huán)，所以染色過程是一定不會(huì)發(fā)生矛盾的。

時(shí)間復(fù)雜度是$O(n+m)$ ， n 表示點(diǎn)數(shù)，m 表示邊數(shù)。

例題：860. 染色法判定二分圖

https://www.acwing.com/activity/content/problem/content/926/

使用 dfs 對(duì)圖中各個(gè)節(jié)點(diǎn)染色，染色過程中不發(fā)生沖突即為二分圖。

import java.util.*;

public class Main {
    static final int N = 100005;
    static List<Integer>[] g = new ArrayList[N];
    static int[] color = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        // 建圖
        Arrays.setAll(g, e -> new ArrayList<Integer>());
        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt(), v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);
        }

        // 圖可能由多個(gè)非連通的子圖構(gòu)成。因此，應(yīng)該對(duì)每一個(gè)尚未訪問過的點(diǎn)都進(jìn)行一次深度優(yōu)先搜索。
        boolean f = true;
        for (int i = 1; i <= n; ++i) {
            if (color[i] == 0 && !dfs(i, 1)) {
                f = false;
                break;
            }
        }
        System.out.println(f? "Yes": "No");
    }

    static boolean dfs(int x, int c) {
        boolean res = true;
        color[x] = c;
        for (int y: g[x]) {
            if (color[y] == 0) res &= dfs(y, 3 - c);
            else if (color[y] == color[x]) return false;
        }
        return res;
    }
}

匈牙利匹配

二分圖最大匹配

**二分圖最大匹配**：
翻譯成人話就是——
給定一個(gè)二分圖 G，即分左右兩部分，各部分之間的點(diǎn)沒有邊連接，要求選出一些邊，使得這些邊沒有公共頂點(diǎn)，且邊的數(shù)量最大。

匈牙利匹配算法思想

兩個(gè)集合的點(diǎn)數(shù)分別是 n1 , n2。
枚舉 n1 ， 嘗試 i 是否可以找到一個(gè) j 完成匹配，匹配成功就 ++cnt。

所以重點(diǎn)是 find(i) 方法：
對(duì)每個(gè) i ，枚舉 i 相鄰的所有 j —— 如果 j 沒有被匹配就直接返回 true；如果 j 被匹配了，就嘗試現(xiàn)在和 j 匹配的另一個(gè) i 能不能換一個(gè) j，能換就換一個(gè)然后返回 true；否則返回 false。

時(shí)間復(fù)雜度是 $O(n?m)$，n 表示點(diǎn)數(shù)，m 表示邊數(shù)。

例題：861. 二分圖的最大匹配

https://www.acwing.com/activity/content/problem/content/927/

重點(diǎn)是理解數(shù)組 match 和 st 的含義，以及方法 find(x) 的寫法和使用。

import java.util.*;

public class Main {
    static final int N = 505;
    static int[][] g = new int[N][N];
    static int[] match = new int[N];		// match記錄集合2中各個(gè)點(diǎn)匹配的集合1的點(diǎn)是哪個(gè)
    static boolean[] st = new boolean[N];	// st表示集合2中的點(diǎn)有沒有被匹配
    static int n1, n2;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n1 = sc.nextInt();
        n2 = sc.nextInt();
        int m = sc.nextInt();
        // 建圖
        for (int i = 0; i < m; ++i) {
            int u = sc.nextInt(), v = sc.nextInt();
            g[u][v] = 1;        // 左邊的 u 和 右邊的 v 之間有一條邊
        }

        int cnt = 0;
        for (int i = 1; i <= n1; ++i) {
            Arrays.fill(st, false);		// 重置st
            if (find(i)) ++cnt;
        }

        System.out.println(cnt);
    }

    static boolean find(int x) {
        for (int j = 1; j <= n2; ++j) {
            if (!st[j] && g[x][j] == 1) {
                st[j] = true;
                // 如果 j 還沒有匹配或者當(dāng)前使用 j 的 x 可以讓出去
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }
}

相關(guān)題目

785. 判斷二分圖

https://leetcode.cn/problems/is-graph-bipartite/description/

在這里插入代碼片

LCR 106. 判斷二分圖

https://leetcode.cn/problems/vEAB3K/description/

文章來源地址http://www.zghlxwxcb.cn/news/detail-601474.html

在這里插入代碼片

到了這里，關(guān)于【算法基礎(chǔ)：搜索與圖論】3.6 二分圖（染色法判定二分圖&匈牙利算法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！