9. Αντιγραφή Κατά τη διάρκεια μιας εξέτασης, ο καθηγητής Floyd παρατήρησε ότι ορισμένοι φοιτητές ανταλλάσσουν σημειώσεις. Αρχικά, ήθελε να τους δώσει όλους βαθμό 2, αλλά ο καθηγητής ήταν ευγενικός και αποφάσισε να χωρίσει τους φοιτητές σε δύο ομάδες: αυτούς που επιτρέπουν την αντιγραφή και να δώσει μόνο στην πρώτη ομάδα βαθμό 2. Ο καθηγητής έχει καταγράψει όλα τα ζευγάρια φοιτητών που αντάλλαξαν σημειώσεις. Είναι απαραίτητο να καθοριστεί αν μπορεί να χωρίσει τους φοιτητές σε δύο ομάδες έτσι ώστε κάθε ανταλλαγή σημειώσεων να πραγματοποιείται από φοιτητή μιας ομάδας σε φοιτητή της άλλης ομάδας. Μορφή εισόδου Στην πρώτη γραμμή βρίσκονται δύο αριθμοί N και M — ο αριθμός των φοιτητών και ο αριθμός των ζευγαριών φοιτητών που αντάλλαξαν σημειώσεις (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Στη συνέχεια, σε M γραμμές, περιγράφονται τα ζευγάρια φοιτητών: δύο αριθμοί που αντιστοιχούν στους αριθμούς των φοιτητών που αντάλλαξαν σημειώσεις (η αρίθμηση των φοιτητών ξεκινά από 1, κάθε ζευγάρι φοιτητών αναγράφεται όχι περισσότερο από μία φορά). Μορφή εξόδου Πρέπει να εκτυπωθεί η απάντηση στην εργασία του καθηγητή Floyd. Αν είναι δυνατό να χωρίσει τους φοιτητές σε δύο ομάδες, εκτυπώστε YES; διαφορετικά, 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", значит профессор сможет разделить студентов на две группы, иначе — нет.