Intern

9. Kopijavimas Testo metu profesorius Floyd pastebėjo, kad kai kurie studentai keičiasi pastabomis. Iš pradžių jis norėjo visiems duoti 2 balus, tačiau profesorius buvo geranoriškas, todėl nusprendė studentus padalinti į dvi grupes: tų, kurie leidžia kopijuoti, ir tik pirmos grupės duoti 2 balus. Profesorius užregistravo visas studentų poras, kurios keitėsi pastabomis. Reikia nustatyti, ar galima studentus padalinti į dvi grupes taip, kad bet koks pastabų keitimas vyktų iš vienos grupės studento į kitos grupės studentą. Įvesties formatas Pirmoje eilutėje yra du skaičiai N ir M — studentų skaičius ir studentų porų, kurios keitėsi pastabomis, skaičius (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Tolesnėse M eilutėse aprašyti studentų poros: du skaičiai, atitinkantys studentų numerius, kurie keitėsi pastabomis (studentų numeriai prasideda nuo 1, kiekviena pora yra išvardyta ne daugiau kaip vieną kartą). Išvesties formatas Reikia išspausdinti profesoriaus Floyd užduoties atsaką. Jei įmanoma studentus padalinti į dvi grupes, rašykite YES; kitaip, NO.

sobes.tech AI

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

Ankstesnis Kitas