Intern

9. Másolás A vizsgán Floyd professzor észrevette, hogy néhány diák jegyzeteket cserél. Kezdetben mindenki számára 2-es osztályzatot akart adni, de a professzor kedves volt, ezért úgy döntött, két csoportra osztja a diákokat: azok, akik engedélyezik a másolást, és csak az első csoportnak adnak 2-es osztályzatot. A professzor rögzítette az összes párosítást a diákok között, akik jegyzeteket cseréltek. Meg kell határozni, hogy lehet-e a diákokat két csoportra osztani úgy, hogy minden jegyzetcsere egyik csoport egyik diákjától a másik csoport egyik diákjához történjen. Bemeneti formátum Az első sorban két szám található: N és M — a diákok száma és a jegyzeteket cserélő párok száma (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Ezután M sorban találhatók a párok leírásai: két szám, amelyek megfelelnek a jegyzeteket cserélő diákok számainak (a diákok számozása 1-től kezdődik, minden párt legfeljebb egyszer listáznak). Kimeneti formátum A Floyd professzor feladatának válaszát kell kiírni. Ha lehetséges a diákokat két csoportra osztani, írja be az YES-t; különben, NO.

sobes.tech MI

Válasz az MI-től

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

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

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

Korábbi Következő