题解 | #二分图判定#

题目链接

二分图判定

题目描述

给定一个包含 $n$ 个节点和 $m$ 条边的无向图。如果能将图中的节点染成黑白两种颜色，使得每条边的两个端点颜色都不同，那么这个图就被称为二分图。

任务是判断给定的图是否为二分图。

解题思路

判断一个图是否为二分图的经典方法是染色法。一个图是二分图，当且仅当它不包含任何奇数长度的环。我们可以通过图遍历（如广度优先搜索 BFS 或深度优先搜索 DFS）来模拟这个染色过程。

算法的核心思想是：尝试用两种颜色（例如，颜色 1 和颜色 2）对图中的节点进行染色。从任意一个未被染色的节点开始遍历，将其染成颜色 1。然后，将其所有相邻的节点染成颜色 2。再将与颜色 2 的节点相邻的未染色节点染成颜色 1，以此类推。

在遍历过程中，如果遇到一个已经被染色的相邻节点，我们就检查它的颜色。如果这个相邻节点的颜色与当前节点的颜色相同，说明这两个直接相连的节点颜色冲突了。这也就意味着图中存在一个奇数长度的环，因此该图不是二分图。

由于给定的图可能是不连通的（由多个独立的连通分量组成），我们需要对每个连通分量都执行一次染色检查。

算法步骤如下：

初始化：
- 构建图的邻接表。
- 创建一个 $color$ 数组，大小为 $n+1$ ，用于存储每个节点的颜色。初始时所有值设为 0，表示“未染色”。
遍历所有节点：
- 从节点 1 到 $n$ 进行循环。
- 如果当前节点 $i$ 尚未被染色（ $color[i] = 0$ ），说明我们发现了一个新的连通分量。从这个节点开始执行一次染色过程（例如，使用 BFS）。
BFS 染色过程：
- 创建一个队列，并将起始节点 $i$ 加入队列。将其染上第一种颜色（ $color[i] = 1$ ）。
- 当队列不为空时，出队一个节点 $u$ 。
- 遍历 $u$ 的所有邻居节点 $v$ ：
  - 如果 $v$ 未被染色（ $color[v] = 0$ ），则将其染成与 $u$ 相反的颜色（ $color[v] = 3 - color[u]$ ），并将其入队。
  - 如果 $v$ 已经被染色，检查 $color[v]$ 是否与 $color[u]$ 相同。如果相同，则发生冲突，说明图不是二分图，可以直接返回 "No"。
最终结果：
- 如果遍历完所有节点及其连通分量都没有发现任何颜色冲突，则说明该图是二分图，返回 "Yes"。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool isBipartite(int n, const vector<vector<int>>& adj) {
    vector<int> color(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        if (color[i] == 0) {
            queue<int> q;
            q.push(i);
            color[i] = 1;

            while (!q.empty()) {
                int u = q.front();
                q.pop();

                for (int v : adj[u]) {
                    if (color[v] == 0) {
                        color[v] = 3 - color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (isBipartite(n, adj)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        if (isBipartite(n, adj)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    private static boolean isBipartite(int n, ArrayList<Integer>[] adj) {
        int[] color = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                color[i] = 1;

                while (!q.isEmpty()) {
                    int u = q.poll();
                    for (int v : adj[u]) {
                        if (color[v] == 0) {
                            color[v] = 3 - color[u];
                            q.add(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

from collections import deque

def is_bipartite(n, adj):
    color = [0] * (n + 1)
    for i in range(1, n + 1):
        if color[i] == 0:
            q = deque([i])
            color[i] = 1
            while q:
                u = q.popleft()
                for v in adj[u]:
                    if color[v] == 0:
                        color[v] = 3 - color[u]
                        q.append(v)
                    elif color[v] == color[u]:
                        return False
    return True

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

if is_bipartite(n, adj):
    print("Yes")
else:
    print("No")

算法及复杂度

算法：图的二分图判定（染色法），通常通过广度优先搜索（BFS）或深度优先搜索（DFS）实现。
时间复杂度： $O(n+m)$ ，其中 $n$ 是节点数， $m$ 是边数。因为每个节点和每条边在遍历过程中最多被访问一次。
空间复杂度： $O(n+m)$ ，主要用于存储图的邻接表、颜色数组以及 BFS 使用的队列。