Intern

9. Abschreiben Während einer Kontrolle bemerkte Professor Floyd, dass einige Studenten Notizen austauschten. Zuerst wollte er allen eine 2 geben, aber der Professor war freundlich, also beschloss er, die Studenten in zwei Gruppen zu teilen: diejenigen, die abschreiben lassen, und nur die ersten mit einer 2 bewerten. Der Professor hat alle Paare von Studenten notiert, die Notizen ausgetauscht haben. Es ist notwendig zu bestimmen, ob er die Studenten in zwei Gruppen aufteilen kann, so dass jeder Notenaustausch zwischen einem Studenten einer Gruppe und einem Studenten der anderen Gruppe erfolgt. Eingabeformat Im ersten Zeile stehen zwei Zahlen N und M — die Anzahl der Studenten und die Anzahl der Paare von Studenten, die Notizen austauschen (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Danach folgen in M Zeilen die Beschreibungen der Paare von Studenten: zwei Zahlen, die den Nummern der Studenten entsprechen, die Notizen austauschen (die Nummerierung der Studenten beginnt bei 1, jedes Paar wird höchstens einmal aufgelistet). Ausgabeformat Es ist notwendig, die Antwort auf die Aufgabe von Professor Floyd auszugeben. Wenn es möglich ist, die Studenten in zwei Gruppen zu teilen, geben Sie YES aus; andernfalls NO.

sobes.tech KI

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

Zurück Als nächstes