染色法判别二分圖

大雪菜的課（筆記）

搜尋與圖論（三）

3.染色法判别二分圖

(1).模闆(染色法判别二分圖 —— 模闆題 AcWing 860. 染色法判定二分圖)

時間複雜度是 O(n+m)O(n+m), nn 表示點數，mm 表示邊數

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

// 參數：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] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

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

AcWing860. 染色法判定二分圖

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

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

輸入格式

第一行包含兩個整數n和m。

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

輸出格式

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

資料範圍

1≤n,m≤105

輸入樣例：

4 4

1 3

1 4

2 3

2 4

輸出樣例：

Yes

#include <iostream>
#include <string.h>
using namespace std;
const int N=100010,M=200010;
int e[M],ne[M],h[N],idx;
int color[N];
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]){
            if(!dfs(j,3-c)) return false;
        }else if(color[j]==c)   return false;
    }
    return true;
}
int main()
{
    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;
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){
                flag=false;
                break;
            }
        }
    }
    if(flag)    cout<<"Yes";
    else    cout<<"No";
    return 0;
}