Intern

9. Kópia Počas skúšky si profesor Floyd všimol, že niektorí študenti si vymieňajú poznámky. Najprv chcel všetkým dať dvojky, ale profesor bol láskavý, a tak sa rozhodol študentov rozdeliť do dvoch skupín: tých, ktorí umožňujú kopírovanie, a tým, ktorým dáva iba prvú skupinu s dvojkami. Profesor zaznamenal všetky páry študentov, ktorí si vymieňali poznámky. Je potrebné určiť, či je možné študentov rozdeliť do dvoch skupín tak, aby každá výmena poznámok prebiehala od študenta jednej skupiny k študentovi druhej skupiny. Formát vstupu V prvej riadke sú dve čísla N a M — počet študentov a počet párov študentov, ktorí si vymieňali poznámky (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Ďalej v M riadkoch sú popísané páry študentov: dve čísla, ktoré zodpovedajú číslam študentov, ktorí si vymieňali poznámky (číslovanie študentov začína od 1, každý pár je uvedený nie viac ako raz). Formát výstupu Je potrebné vypísať odpoveď na úlohu profesora Floyd. Ak je možné študentov rozdeliť do dvoch skupín, vypíšte YES; inak, NO.

sobes.tech AI

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

Predchádzajúce Ďalej