Intern

9. Нусха Тести учурунда профессор Флойд кээ бир студенттердин белектер алмашканын байкады. Башында алгыс, ал бардык студенттерге 2 балл коюуну каалаган, бирок профессор мээримдүү болчу, жана студенттерди эки топко бөлүүгө чечим кабыл алды: копиялоого уруксат бергендер жана биринчи топко гана 2 балл коюу. Профессор бардык студенттердин алмашкан экижуптуулүгүн жазып алган. Студенттерди эки топко бөлүү мүмкүнчүлүгүн аныктоо керек, ошондо ар бир белек алмашуу бир топтун студентинен экинчи топтун студентине өтөт. Кирүү форматы Биринчи сапта эки сан 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", значит профессор сможет разделить студентов на две группы, иначе — нет.

Мурунку Кийинки