Intern

9. Нусха Дар вақти имтиҳон, профессори Флойд дарк кард, ки баъзе донишҷӯён ёддоштҳоро мубодила мекунанд. Аввал, ӯ мехост ба ҳама ду хол диҳад, аммо профессори меҳрубон буд, ва қарор дод, ки донишҷӯёнро ба ду гурӯҳ тақсим кунад: онҳое, ки нусха гирифтанро иҷозат медиҳанд, ва танҳо ба аввал ду хол медиҳанд. Професор ҳамаи ҷуфтҳои донишҷӯёнро, ки ёддоштҳоро мубодила карданд, сабт кардааст. Мушкил аст, ки муайян кунад, оё мумкин аст донишҷӯёнро ба ду гурӯҳ тақсим кард, то ки ҳар як мубодилаи ёддошт аз донишҷӯи як гурӯҳ ба донишҷӯи гурӯҳи дигар сурат гирад. Формати воридот Дар сатри аввал ду рақам N ва M ҷойгир шудаанд — шумораи донишҷӯён ва шумораи ҷуфтҳои донишҷӯён, ки ёддоштҳоро мубодила карданд (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Баъд аз он, дар M сатр, тавсифи ҷуфтҳои донишҷӯён оварда шудааст: ду рақам, ки ба рақамҳои донишҷӯён, ки ёддоштҳоро мубодила карданд, мувофиқат мекунанд (нумератсияи донишҷӯён аз 1 оғоз мешавад, ҳар ҷуфт донишҷӯён на бештар аз як маротиба рӯйхат карда мешавад). Формати баромад Мавзӯъро бояд ҷавоб дод. Агар имконпазир бошад, ки донишҷӯёнро ба ду гурӯҳ тақсим кард, YES нависед; дар ғайри ҳол, NO.

sobes.tech AI

Ҷавоб аз AI

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

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

Представить студентов как вершины графа, а пары обмена записками — как рёбра.
Попытаться раскрасить граф в два цвета (например, 0 и 1), так чтобы соседние вершины имели разные цвета.
Если при обходе графа (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", значит профессор сможет разделить студентов на две группы, иначе — нет.

Гузашта Оянда