演算法競賽——二分圖及應用

• 2022 年 1 月 15 日
• 筆記

二分圖

二分圖簡介

定義：

簡而言之，就是頂點集V可分割為兩個互不相交的子集，並且圖中每條邊依附的兩個頂點都分屬於這兩個互不相交的子集，兩個子集內的頂點不相鄰。——百度百科

辨析示例

區別二分圖，關鍵是看點集是否能分成兩個獨立的點集。

圖1中U和V構造的點集所形成的循環圈不為奇數，所以是二分圖。

圖2中U和V和W構造的點集所形成的的循環圈為奇數，所以不是二分圖。

1.染色法判斷二分圖

判定：

二分圖是這樣一個圖： 有兩頂點集且圖中每條邊的的兩個頂點分別位於兩個頂點集中，每個頂點集中沒有邊直接相連接！

無向圖G為二分圖的充分必要條件是，G至少有兩個頂點,且其所有迴路的長度均為偶數。

判斷二分圖的常見方法是染色法： 開始對任意一未染色的頂點染色，之後判斷其相鄰的頂點中，若未染色則將其染上和相鄰頂點不同的顏色， 若已經染色且顏色和相鄰頂點的顏色相同則說明不是二分圖，若顏色不同則繼續判斷，bfs和dfs可以搞定！

演算法模板

int n;      // n表示點數
int h[N], e[M], ne[M], idx;     // 鄰接表存儲圖
int color[N];       // 表示每個點的顏色，0表示未染色，1表示白色，2表示黑色

// 參數：u表示當前節點，c表示當前點的顏色
bool dfs(int u, int c)
{
    color[u] = c;//記錄顏色
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])//如果沒染過顏色
        {
            //dfs深搜 染色 1 或者 2
            //如果不可以將j成功染色
            if(!dfs(j, 3 - c)) return false;
        }
        else if(color[j] == c) return false; //如果染過顏色且和c相同
    }
    
    return true;
}

bool check()
{

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
    return flag;
}

例題

【acwing 860染色法判定二分圖】

給定一個 nn 個點 mm 條邊的無向圖，圖中可能存在重邊和自環。

請你判斷這個圖是否是二分圖。

輸入格式

第一行包含兩個整數 nn 和 mm。

接下來 mm 行，每行包含兩個整數 uu 和 vv，表示點 uu 和點 vv 之間存在一條邊。

輸出格式

如果給定圖是二分圖，則輸出 Yes，否則輸出 No。

數據範圍

1≤n,m≤1051≤n,m≤105

輸入樣例：

4 4
1 3
1 4
2 3
2 4

輸出樣例：

Yes

DFS版本程式碼思路：

• 染色可以使用1和2區分不同顏色，用0表示未染色
• 遍歷所有點，每次將未染色的點進行dfs, 默認染成1或者2
• 由於某個點染色成功不代表整個圖就是二分圖,因此只有某個點染色失敗才能立刻break/return
  • 染色失敗相當於存在相鄰的2個點染了相同的顏色

【參考程式碼】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int color[N];
int n, m;

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

bool dfs(int u, int c)
{
    color[u] = c;//記錄顏色
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])//如果沒染過顏色
        {
            //dfs深搜 染色 1 或者 2
            //如果不可以將j成功染色
            if(!dfs(j, 3 - c)) return false;
        }
        else if(color[j] == c) return false; //如果染過顏色且和c相同
    }
    
    return true;
}

int main()
{
    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;
    for(int i = 1; i <= n; i ++)
    {
        if(!color[i])//如果這個點未染色
        {
            if(!dfs(i, 1))//dfs過程中要是返回false——有矛盾發生，不是二分圖
            {
                flag = false;
                break;
            }
            //不發生矛盾則繼續搜
        }
    }
    
    if(flag) puts("Yes");
    else puts("No");
    
    return 0;
}

2. 二分圖的最大匹配——匈牙利演算法

導讀

要了解匈牙利演算法必須先理解下面的概念：

匹配：在圖論中，一個「匹配」是一個邊的集合，其中任意兩條邊都沒有公共頂點。

最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。

【匹配】

【最大匹配】

註：最大匹配結果可能不唯一，但最大匹配數一樣！

演算法模板

//match[j]=a,表示女孩j的現有配對男友是a
int match[N];
//st[]數組我稱為臨時預定數組，st[j]=a表示一輪模擬匹配中，女孩j被男孩a預定了。
int st[N];

//這個函數的作用是用來判斷,如果加入x來參與模擬配對,會不會使匹配數增多(能不能給x男孩找到對象)
bool find(int x)
{
    //遍歷自己喜歡的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在這一輪模擬匹配中,這個女孩尚未被預定
        {
            st[j] = true;//那x就預定這個女孩了
            //如果女孩j沒有男朋友，或者她原來的男朋友能夠預定其它喜歡的女孩（原來的男朋友還有備胎選）。配對成功,更新match
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被預定了。配對失敗。
    return false;
}

//記錄最大匹配（遍歷遍歷所有男孩 給他找對象）
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{  
    //因為每次模擬匹配的預定情況都是不一樣的所以每輪模擬都要初始化
    memset(st,false,sizeof st);
    if(find(i)) 
        res++;
}  

例題

【acwing 861 二分圖的最大匹配】

給定一個二分圖，其中左半部包含 n1 個點（編號 1∼n1），右半部包含 n2 個點（編號 1∼n2），二分圖共包含 m 條邊。

數據保證任意一條邊的兩個端點都不可能在同一部分中。

請你求出二分圖的最大匹配數。

二分圖的匹配：給定一個二分圖 G，在 G 的一個子圖 M 中，M 的邊集{E} 中的任意兩條邊都不依附於同一個頂點，則稱 M 是一個匹配。

二分圖的最大匹配：所有匹配中包含邊數最多的一組匹配被稱為二分圖的最大匹配，其邊數即為最大匹配數。

輸入格式

第一行包含三個整數 n1、 n2 和 m。

接下來 m 行，每行包含兩個整數 u和 vv，表示左半部點集中的點 u 和右半部點集中的點 vv 之間存在一條邊。

輸出格式

輸出一個整數，表示二分圖的最大匹配數。

數據範圍

1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105

輸入樣例：

2 2 4
1 1
1 2
2 1
2 2

輸出樣例：

2

【參考程式碼】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 1e5 + 10;

int h[N], e[M], ne[M], idx;
int match[N];//匹配數組
bool st[N];//預定女友數組

int n1, n2, m;

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(!st[j])//如果女孩j沒被預定
        {
            st[j] = true;//預定女孩j
            //如果女孩j沒有男朋友，或者她原來的男朋友還有其他預定對象（還有備胎）。配對成功
            if(!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
     //自己中意的全部都被預定了。配對失敗。
    return false;
}
int main()
{
    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, 0, sizeof st);
        if(find(i))
            res ++;
    }
    
    cout << res;
    
    return 0;
}

總結

在理解思路的基礎上，學習總結程式碼！

學習內容源自：
百度百科
acwing演算法基礎課
嗶哩嗶哩：無權二分圖匹配

註：如果文章有任何錯誤或不足，請各位大佬盡情指出，評論留言留下您寶貴的建議！如果這篇文章對你有些許幫助，希望可愛親切的您點個贊推薦一手，非常感謝啦