Intern

9. Copie Pendant un contrôle, le professeur Floyd a remarqué que certains étudiants échangeaient des notes. Au début, il voulait leur donner tous la note de 2, mais le professeur était gentil, alors il a décidé de diviser les étudiants en deux groupes : ceux qui permettent de copier, et donner des notes de 2 uniquement aux premiers. Le professeur a enregistré toutes les paires d'étudiants qui ont échangé des notes. Il faut déterminer s'il est possible de diviser les étudiants en deux groupes de manière que tout échange de notes se fasse d'un étudiant d'un groupe à un étudiant de l'autre groupe. Format d'entrée La première ligne contient deux nombres N et M — le nombre d'étudiants et le nombre de paires d'étudiants échangeant des notes (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Ensuite, dans M lignes, sont décrites les paires d'étudiants : deux nombres correspondant aux numéros des étudiants échangeant des notes (la numérotation des étudiants commence à 1, chaque paire d'étudiants est listée au plus une fois). Format de sortie Il faut afficher la réponse à la tâche du professeur Floyd. Si il est possible de diviser les étudiants en deux groupes, affichez YES ; sinon, NO.

sobes.tech IA

Réponse de l'IA

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

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

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

Précédent Suivant