题目描述

染色法判定二分图

样例

blablabla

算法1

(bfs)

一个点染色，另外一个点染不同颜色，如果冲突说明不是二分图。

时间复杂度分析：不大

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2e5+2;

int n, m;
int e[N],h[N], ne[N], idx;
int color[N];

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

bool bfs(int u){
    queue<pair<int, int>> q;
    color[u] = 1;
    q.push({u,1});
    while (q.size()){
        int ver = q.front().first;
        int ver_color = q.front().second;
        q.pop();
        for (int i=h[ver]; i!=-1; i=ne[i]){
            int j = e[i];
            if (color[j] == -1) {
                color[j] = ~ver_color;
                q.push({j, color[j]});
            } else if (color[j] == ver_color){
                return false;
            } 
        }
    }
    return true;
}

int main(){
    memset(h, -1, sizeof h);
    memset(color, -1, sizeof color);
    cin >> n >> m;
    while (m--){
        int x, y;
        cin >> x >> y;
        add(x, y); add(y, x);  
    }
    bool flag = true;
    for(int i = 1; i <= n; i ++) {
        if (color[i] == -1){
            if(!bfs(i)){
                flag = false;
                break;
            }
        }
    }
    if (flag) cout << "Yes";
    else cout << "No";
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla