Intern

9. Copiar Durante uma prova, o professor Floyd notou que alguns estudantes trocavam notas. No início, ele quis atribuir a todos a nota 2, mas o professor era gentil, então decidiu dividir os estudantes em dois grupos: os que permitem copiar e os que só recebem notas de 2 no primeiro. O professor tem registradas todas as pares de estudantes que trocaram notas. É necessário determinar se é possível dividir os estudantes em dois grupos de modo que qualquer troca de notas seja feita de um estudante de um grupo para um estudante do outro grupo. Formato de entrada Na primeira linha, encontram-se dois números N e M — a quantidade de estudantes e a quantidade de pares de estudantes que trocam notas (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Depois, em M linhas, estão as descrições dos pares de estudantes: dois números que correspondem aos números dos estudantes que trocam notas (a numeração dos estudantes começa em 1, cada par de estudantes é listado no máximo uma vez). Formato de saída Deve-se imprimir a resposta para a tarefa do professor Floyd. Se for possível dividir os estudantes em dois grupos, imprima YES; caso contrário, NO.

sobes.tech IA

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

Anterior Próximo