题解 | #二分图判定#

题目链接

二分图判定

题目描述

给定一张包含 $n$ 个节点、 $m$ 条无向边的图（不保证连通）。若存在一种黑白二色染色方式，使任意一条边的两个端点颜色不同，则该图为二分图。判断所给图是否为二分图。

输入：

第一行两个整数 $n$ 、 $m$
接下来 $m$ 行，每行两个整数 $u$ 、 $v$ 表示一条无向边

输出：

若该图为二分图，输出 Yes；否则输出 No

解题思路

对每个未染色的连通分量，任选一点开始 BFS/DFS 染色，使用两种颜色交替赋值。
遍历边时若发现相邻两点颜色相同，则不是二分图。
图可能不连通，需从每个未染色点启动一次搜索。
复杂度： $\mathcal{O}(n+m)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> color(n + 1, 0); // 0: uncolored, 1/-1: two colors
    queue<int> q;
    for (int s = 1; s <= n; ++s) {
        if (color[s] != 0) continue;
        color[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (color[v] == 0) {
                    color[v] = -color[u];
                    q.push(v);
                } else if (color[v] == color[u]) {
                    cout << "No\n";
                    return 0;
                }
            }
        }
    }
    cout << "Yes\n";
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        int[] color = new int[n + 1]; // 0: uncolored, 1/-1: colors
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int s = 1; s <= n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1;
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : g[u]) {
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.add(v);
                    } else if (color[v] == color[u]) {
                        System.out.println("No");
                        return;
                    }
                }
            }
        }
        System.out.println("Yes");
    }
}

from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

color = [0] * (n + 1)  # 0: uncolored, 1/-1: colors
for s in range(1, n + 1):
    if color[s] != 0:
        continue
    color[s] = 1
    q = deque([s])
    while q:
        u = q.popleft()
        for v in g[u]:
            if color[v] == 0:
                color[v] = -color[u]
                q.append(v)
            elif color[v] == color[u]:
                print('No')
                exit()
print('Yes')

算法及复杂度

算法：多源（逐分量）BFS/DFS 二色染色判定
时间复杂度： $\mathcal{O}(n+m)$
空间复杂度： $\mathcal{O}(n+m)$