题目链接

幼儿园分班

题目描述

一个大班有 N 位小朋友，需要分成两个小班。现在有 M 个请求，每个请求的形式为 (u, v)，表示小朋友 u 和 v 不希望在同一个班。

需要判断是否存在一种分班方案，能够满足所有 M 个请求。如果可以，输出 1，否则输出 0。

解题思路

这是一个经典的图论问题，可以被抽象为二分图判定 (Bipartite Graph Checking)。

1. 问题建模

  • 我们将每个小朋友看作图中的一个节点 (Node)。

  • 对于每个请求 (u, v)，我们在节点 u 和节点 v 之间连接一条边 (Edge)。这条边表示 u 和 v 之间存在“冲突关系”，不能被分到同一个集合。

经过这样的转换，我们就得到了一张包含 N 个节点和 M 条边的无向图。

2. 核心问题转化

现在，原问题“能否将小朋友分成两个班”就等价于新问题：“能否将图的所有节点分成两个独立的集合，使得每条边的两个端点都分别位于不同的集合中？”

这正是二分图的定义。一个图是二分图，当且仅当它可以用两种颜色进行染色，使得每条边的两个端点的颜色都不同。一个重要的性质是：一个图是二分图，当且仅当它不包含任何奇数长度的环。

3. 算法：广度优先搜索 (BFS) 进行二染色

我们可以通过尝试对图进行“二染色”来判断它是否为二分图。

  1. 数据结构：

    • 使用邻接表来存储图。

    • 使用一个 color 数组，大小为 N+1，来记录每个节点的颜色（属于哪个班）。我们可以用 0 表示未染色，1 表示 A 班，-1 表示 B 班。

  2. 算法流程：

    a. 遍历所有节点（小朋友），从 1到 N。因为图可能是由多个不相连的组件构成的，所以需要这个外层循环。

    b. 如果当前节点 i 还未被染色 (color[i] == 0)，说明遇到了一个新的连通分量，我们从这个节点开始进行 BFS 染色。

    c. BFS 染色过程:

    • 将节点 i 染成颜色 1，并将其加入队列。

    • 当队列不为空时，出队一个节点 u。

    • 遍历 u 的所有邻居 v：

    • 如果 v 未被染色 (color[v] == 0)，则将其染成与 u 相反的颜色 (color[v] = -color[u])，并入队。

    • 如果 v 已经被染色，并且其颜色与 u 相同 (color[v] == color[u])，则说明发生了颜色冲突。这意味着图中存在一个奇数环，因此它不是二分图。我们可以立即返回 false（不可行）。

    d. 如果 BFS 过程顺利完成，说明当前连通分量是二分的。我们继续外层循环，检查下一个连通分量。

  3. 结论：

    • 如果在整个过程中都没有发现颜色冲突，说明整个图是二分图，可以满足所有分班要求，返回 true（可行）。

代码

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

using namespace std;

bool isBipartite(int n, const vector<vector<int>>& adj) {
    vector<int> colors(n + 1, 0); // 0: uncolored, 1: color A, -1: color B

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

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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 << 1 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
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();

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

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

        if (isBipartite(n, adj)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
        
        sc.close();
    }

    private static boolean isBipartite(int n, List<List<Integer>> adj) {
        int[] colors = new int[n + 1]; // 0: uncolored, 1: color A, -1: color B

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

                while (!q.isEmpty()) {
                    int u = q.poll();

                    for (int v : adj.get(u)) {
                        if (colors[v] == 0) {
                            colors[v] = -colors[u];
                            q.add(v);
                        } else if (colors[v] == colors[u]) {
                            return false; // Conflict
                        }
                    }
                }
            }
        }
        return true;
    }
}

import sys
from collections import deque

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        m_str = sys.stdin.readline()
        if not m_str: return
        m = int(m_str)
        
        adj = [[] for _ in range(n + 1)]
        for _ in range(m):
            u, v = map(int, sys.stdin.readline().split())
            adj[u].append(v)
            adj[v].append(u)

        if is_bipartite(n, adj):
            print(1)
        else:
            print(0)

    except (IOError, ValueError):
        return

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

solve()

算法及复杂度

  • 算法：图论、二分图判定、广度优先搜索 (BFS)

  • 时间复杂度: ，其中 N 是小朋友的数量（节点数），M 是请求的数量（边数）。这是因为我们需要遍历所有节点和所有边一次来进行 BFS 染色。

  • 空间复杂度: ，用于存储图的邻接表、colors 数组以及 BFS 队列。