Intern

9. Копирање Током испита, професор Флойд је приметио да неки студенти размењују белешке. У почетку, желео је да свима постави двојке, али професор је био љубазан, па је одлучио да студенте подели у две групе: оне који дозвољавају копирање и да прво даје двојке. Професор је забележио све парове студената који су размењивали белешке. Потребно је одредити да ли може да подели студенте у две групе тако да свака размена белешки буде од студента једне групе до студента друге групе. Формат улаза У првом реду су два броја N и M — број студената и број парова студената који су размењивали белешке (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Затим, у M редова, описани су парови студената: два броја који одговарају бројевима студената који су размењивали белешке (нумерација студената почиње од 1, сваки пар студената је наведена не више од једном). Формат излаза Потребно је исписати одговор на задатак професора Флоида. Ако је могуће поделити студенте у две групе - испишите YES; иначе, NO.

sobes.tech АИ

Одговор од АИ

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

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

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

Претходно Следеће