9. Copia Durante un esame, il professor Floyd ha notato che alcuni studenti si scambiavano appunti. All'inizio voleva mettere a tutti un 2, ma il professore era gentile, quindi ha deciso di dividere gli studenti in due gruppi: quelli che consentono di copiare e di mettere solo il primo gruppo con un 2. Il professore ha registrato tutte le coppie di studenti che si sono scambiati appunti. È necessario determinare se è possibile dividere gli studenti in due gruppi in modo che ogni scambio di appunti avvenga da uno studente di un gruppo a uno dell'altro. Formato di input Nella prima riga ci sono due numeri N e M — il numero di studenti e il numero di coppie di studenti che si scambiano appunti (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Successivamente, in M righe, sono descritte le coppie di studenti: due numeri corrispondenti ai numeri degli studenti che si scambiano appunti (la numerazione degli studenti inizia da 1, ogni coppia di studenti viene elencata non più di una volta). Formato di output Deve essere stampata la risposta al problema del professore Floyd. Se è possibile dividere gli studenti in due gruppi, stampa YES; altrimenti, 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", значит профессор сможет разделить студентов на две группы, иначе — нет.