9. Copiat În timpul unui examen, profesorul Floyd a observat că unii studenți schimbă notițe. La început, a vrut să le pună tuturor nota 2, dar profesorul a fost amabil și a decis să împartă studenții în două grupuri: cei care permit copierea și să pună doar primului grup nota 2. Profesorul a înregistrat toate perechile de studenți care au schimbat notițe. Este necesar să se determine dacă poate împărți studenții în două grupuri astfel încât orice schimb de notițe să se realizeze de la un student al unui grup la un student al celuilalt grup. Formatul de intrare În prima linie se află două numere N și M — numărul de studenți și numărul de perechi de studenți care schimbă notițe (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Apoi, în M linii, sunt descrise perechile de studenți: două numere corespunzătoare numerelor studenților care schimbă notițe (numerotarea studenților începe de la 1, fiecare pereche de studenți este listată nu mai mult de o dată). Formatul de ieșire Este necesar să se afișeze răspunsul la sarcina profesorului Floyd. Dacă este posibil să împartă studenții în două grupuri, se afișează YES; altfel, 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", значит профессор сможет разделить студентов на две группы, иначе — нет.