Intern

9. Kopírování Během kontroly si profesor Floyd všiml, že někteří studenti si vyměňují poznámky. Nejprve chtěl všem dát dvojku, ale profesor byl laskavý, a proto se rozhodl studenty rozdělit do dvou skupin: ty, kteří umožňují kopírování, a těm, kterým dá pouze první skupině dvojku. Profesor má zaznamenány všechny páry studentů, kteří si vyměnili poznámky. Je třeba určit, zda je možné studenty rozdělit do dvou skupin tak, aby každá výměna poznámek probíhala od studenta jedné skupiny ke studentovi druhé skupiny. Formát vstupu V první řádce jsou dvě čísla N a M — počet studentů a počet párů studentů, kteří si vyměnili poznámky (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Dále v M řádcích jsou popsány páry studentů: dvě čísla odpovídající číslům studentů, kteří si vyměnili poznámky (číslování studentů začíná od 1, každý pár je uveden nejvýše jednou). Formát výstupu Je třeba vypsat odpověď na úlohu profesora Floyd. Pokud je možné studenty rozdělit do dvou skupin, napište YES; jinak, NO.

sobes.tech AI

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

Předchozí Další