Intern

9. Kopēšana Testa laikā profesors Floyd pamanīja, ka daži studenti apmainās ar piezīmēm. Sākumā viņš vēlējās visiem uzlikt divniekus, bet profesors bija laipns, un nolēma studentus sadalīt divās grupās: tiem, kas ļauj kopēt, un tikai pirmajai grupai uzlikt divniekus. Professors ir reģistrējis visas studentu pārus, kas apmainījās ar piezīmēm. Ir jānoskaidro, vai ir iespējams studentus sadalīt divās grupās tā, lai katra piezīmju apmaiņa notiktu no viena grupas studenta uz otra grupas studentu. Ievades formāts Pirmā rindā ir divi skaitļi N un M — studentu skaits un studentu pāru skaits, kas apmainījās ar piezīmēm (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Tālāk, M rindās ir aprakstīti studentu pāri: divi skaitļi, kas atbilst studentu numuriem, kas apmainījās ar piezīmēm (studentu numerācija sākas no 1, katrs pāris ir uzskaitīts ne vairāk kā vienu reizi). Izvades formāts Ir jāizdrukā profesora Floyd uzdevuma atbilde. Ja ir iespējams studentus sadalīt divās grupās, rakstiet YES; citādi, NO.

sobes.tech AI

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

Iepriekšējais Tālāk