Intern

9. Kopiowanie Podczas egzaminu profesor Floyd zauważył, że niektórzy studenci wymieniają się notatkami. Na początku chciał wszystkim wystawić dwójki, ale profesor był uprzejmy, więc postanowił podzielić studentów na dwie grupy: tych, którzy pozwalają na kopiowanie, i tych, którym wystawia się tylko dwójki na początku. Profesor zanotował wszystkie pary studentów, którzy wymieniali się notatkami. Należy ustalić, czy można podzielić studentów na dwie grupy tak, aby każda wymiana notatek odbywała się od studenta jednej grupy do studenta drugiej grupy. Format wejścia W pierwszej linii znajdują się dwie liczby N i M — liczba studentów i liczba par studentów wymieniających się notatkami (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Następnie, w M liniach, opisane są pary studentów: dwie liczby odpowiadające numerom studentów wymieniających się notatkami (numeracja studentów zaczyna się od 1, każda para studentów jest wymieniona nie więcej niż raz). Format wyjścia Należy wyświetlić odpowiedź na zadanie profesora Floyd. Jeśli możliwe jest podzielenie studentów na dwie grupy, wypisz YES; w przeciwnym razie, NO.

sobes.tech AI

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

Poprzednia Dalej