Intern

9. Kopiëren Tijdens een toets merkte professor Floyd dat sommige studenten aantekeningen uitwisselden. In eerste instantie wilde hij iedereen een 2 geven, maar de professor was vriendelijk en besloot de studenten in twee groepen te verdelen: degenen die kopiëren toestaan en alleen de eerste groep een 2 geven. De professor heeft alle paren studenten die aantekeningen uitwisselden genoteerd. Het is nodig te bepalen of hij de studenten in twee groepen kan verdelen zodat elke uitwisseling van aantekeningen plaatsvindt van een student van de ene groep naar een student van de andere groep. Invoerformaat In de eerste regel staan twee getallen N en M — het aantal studenten en het aantal paren studenten die aantekeningen uitwisselden (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Vervolgens, in M regels, worden de paren van studenten beschreven: twee getallen die overeenkomen met de nummers van de studenten die aantekeningen uitwisselden (de nummering van de studenten begint bij 1, elk paar wordt niet meer dan één keer vermeld). Uitvoerformaat Het is nodig het antwoord op de taak van professor Floyd te geven. Als het mogelijk is om de studenten in twee groepen te verdelen, typ dan YES; anders, NO.

sobes.tech AI

Antwoord van 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", значит профессор сможет разделить студентов на две группы, иначе — нет.

Vorige Volgende