Intern

9. Kopeerimine Testi ajal märkis professor Floyd, et mõned õpilased vahetasid märkmeid. Alguses tahtis ta neile kõigile anda 2, kuid professor oli lahke ja otsustas õpilased kaheks rühmaks jagada: neile, kes lubavad koopiat, ja esimesele rühmale anda ainult 2. Professor on registreerinud kõik õpilaste paarid, kes vahetasid märkmeid. On vaja määrata, kas õpilasi saab jagada kaheks rühmaks nii, et iga märkmete vahetamine toimub ühe rühma õpilaselt teise rühma õpilasele. Sissepääsu formaat Esimesel real on kaks arvu N ja M — õpilaste arv ja õpilaste vahetatud paaride arv (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Järgmisel M real on kirjed õpilaste paaridest: kaks arvu, mis vastavad õpilaste numbritele, kes vahetasid märkmeid (õpilaste nummerdus algab 1-st, iga paar on loetletud mitte rohkem kui üks kord). Väljundi formaat On vaja välja printida professor Floydi ülesande vastus. Kui on võimalik õpilasi jagada kaheks rühmaks, kirjutage YES; vastasel juhul, NO.

sobes.tech AI

Vastus AI-lt

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

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

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

Eelmine Edasi