9. Kopya Sınav sırasında, Profesör Floyd bazı öğrencilerin not alışverişinde bulunduğunu fark etti. Başlangıçta hepsine 2 notu vermek istedi, ancak profesör nazikti, bu yüzden öğrencileri iki gruba ayırmaya karar verdi: kopya izni verenler ve sadece ilk gruba 2 notu verenler. Profesör, not alışverişinde bulunan tüm öğrenci çiftlerini kaydetti. Öğrencileri iki gruba ayırıp ayıramayacağını belirlemesi gerekiyor; böylece herhangi bir not alışverişi, bir gruptaki öğrenciden diğer gruptaki öğrenciye yapılmış olur. Giriş formatı İlk satırda iki sayı N ve M bulunur — öğrenci sayısı ve not alışverişinde bulunan öğrenci çiftlerinin sayısı (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Daha sonra, M satırda, öğrenci çiftlerinin açıklamaları yer alır: not alışverişinde bulunan iki öğrenci numarası (öğrenci numaralandırması 1’den başlar, her öğrenci çifti en fazla bir kez listelenir). Çıkış formatı Profesör Floyd’un görevinin cevabını yazdırmanız gerekir. Öğrencileri iki gruba ayırmak mümkünse, YES yazdırın; aksi takdirde 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", значит профессор сможет разделить студентов на две группы, иначе — нет.