9. Copiar Durante un examen, el profesor Floyd notó que algunos estudiantes intercambiaban notas. Al principio, quería ponerles a todos una nota de 2, pero el profesor era amable, así que decidió dividir a los estudiantes en dos grupos: los que permiten copiar y los que solo reciben notas de 2 en el primero. El profesor tiene registradas todas las parejas de estudiantes que intercambiaron notas. Es necesario determinar si puede dividir a los estudiantes en dos grupos de modo que cualquier intercambio de notas se realice de un estudiante de un grupo a un estudiante del otro grupo. Formato de entrada En la primera línea se encuentran dos números N y M — la cantidad de estudiantes y la cantidad de pares de estudiantes que intercambian notas (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Luego, en M líneas, se describen los pares de estudiantes: dos números que corresponden a los números de los estudiantes que intercambian notas (la numeración de los estudiantes comienza en 1, cada par de estudiantes se lista no más de una vez). Formato de salida Debe imprimir la respuesta a la tarea del profesor Floyd. Si es posible dividir a los estudiantes en dos grupos, imprime YES; de lo contrario, NO.

Задача сводится к проверке, можно ли разбить множество студентов на две группы так, чтобы все пары обмена записками были между студентами из разных групп. Это классическая задача проверки двудольности графа.

Алгоритм решения:

1. Представить студентов как вершины графа, а пары обмена записками — как рёбра.
2. Попытаться раскрасить граф в два цвета (например, 0 и 1), так чтобы соседние вершины имели разные цвета.
3. Если при обходе графа (DFS или BFS) возникает конфликт (ребро между вершинами одного цвета), значит разделить нельзя.

Пример на Python:

from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

color = [-1] * N

def bfs(start):
    queue = deque([start])
    color[start] = 0
    while queue:
        u = queue.popleft()
        for w in graph[u]:
            if color[w] == -1:
                color[w] = 1 - color[u]
                queue.append(w)
            elif color[w] == color[u]:
                return False
    return True

is_bipartite = True
for i in range(N):
    if color[i] == -1:
        if not bfs(i):
            is_bipartite = False
            break

print("YES" if is_bipartite else "NO")

Если вывод "YES", значит профессор сможет разделить студентов на две группы, иначе — нет.