题解 | #二分图判定#

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 构建邻接表
    vector<vector<int>> graph(n);
    vector<int> color(n, 0);  // 0表示未染色
    
    // 读入边
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }
    
    // BFS染色
    queue<int> q;
    for(int i = 0; i < n; i++) {
        if(color[i]) continue;  // 已染色的跳过
        
        q.push(i);
        color[i] = 1;  // 初始染色为1
        
        while(!q.empty()) {
            int u = q.front(); q.pop();
            
            // 遍历相邻节点
            for(int v : graph[u]) {
                if(color[v] == 0) {  // 未染色
                    color[v] = (color[u] == 1) ? 2 : 1;  // 染成相反的颜色
                    q.push(v);
                } else if(color[v] == color[u]) {  // 相邻节点颜色相同
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    
    cout << "Yes" << endl;
    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<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 读入边
        for(int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        // BFS染色
        int[] color = new int[n];
        Queue<Integer> q = new LinkedList<>();
        
        for(int i = 0; i < n; i++) {
            if(color[i] != 0) continue;
            
            q.offer(i);
            color[i] = 1;
            
            while(!q.isEmpty()) {
                int u = q.poll();
                for(int v : graph.get(u)) {
                    if(color[v] == 0) {
                        color[v] = color[u] == 1 ? 2 : 1;
                        q.offer(v);
                    } else if(color[v] == color[u]) {
                        System.out.println("No");
                        return;
                    }
                }
            }
        }
        
        System.out.println("Yes");
    }
}

from collections import deque

def is_bipartite(n, edges):
    # 构建邻接表
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)
    
    # BFS染色
    color = [0] * n  # 0表示未染色
    q = deque()
    
    for i in range(n):
        if color[i]: continue
        
        q.append(i)
        color[i] = 1
        
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = 3 - color[u]  # 1变2，2变1
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    
    return True

def main():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v = map(int, input().split())
        edges.append((u, v))
    
    print("Yes" if is_bipartite(n, edges) else "No")

if __name__ == "__main__":
    main()