Решение задачи #9 на Python с Яндекс CodeRun — Списывание

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Списывание.
Сложность: Лёгкая
Статус решения: "Решено".

Условие задачи:
Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.

У профессора записаны все пары студентов, обменявшихся записками. Требуется определить, сможет ли он разделить студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы.

Формат ввода:
В первой строке находятся два числа NN и MM — количество студентов и количество пар студентов, обменивающихся записками (1≤N≤1021≤N≤102, 0≤M≤N(N−1)/20≤M≤N(N−1)/2).

Далее в MM строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 11). Каждая пара студентов перечислена не более одного раза.

Формат вывода:
Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Решение:

Python

import sys
from collections import defaultdict, deque

def main():
    # Чтение ввода
    input = sys.stdin.read
    data = input().splitlines()

    # Количество студентов и пар
    N, M = map(int, data[0].split())

    # Граф для представления обмена записками
    graph = defaultdict(list)

    # Заполняем граф ребрами
    for i in range(1, M + 1):
        u, v = map(int, data[i].split())
        graph[u].append(v)
        graph[v].append(u)

    # Массив для хранения группы каждого студента (-1: не назначена)
    groups = [-1] * (N + 1)

    def bfs(start):
        """Функция BFS для проверки двудольности графа."""
        queue = deque([start])
        groups[start] = 0  # Назначаем стартовую группу

        while queue:
            current = queue.popleft()
            current_group = groups[current]

            for neighbor in graph[current]:
                if groups[neighbor] == -1:  # Если сосед не посещен
                    groups[neighbor] = 1 - current_group  # Назначаем другую группу
                    queue.append(neighbor)
                elif groups[neighbor] == current_group:
                    # Если сосед уже в той же группе, граф не двудольный
                    return False

        return True

    # Проверяем каждую компоненту графа
    for student in range(1, N + 1):
        if groups[student] == -1:  # Если студент не посещен
            if not bfs(student):
                print("NO")
                return

    print("YES")

if __name__ == "__main__":
    main()

Объяснение кода

Ввод и представление графа:
Считываем количество студентов и пар.
Используем defaultdict для представления графа, где ключ — номер студента, а значение — список студентов, с которыми он обменивался записками.

Алгоритм BFS:
BFS используется для проверки, можно ли разделить студентов на две группы.
Студенты, обменявшиеся записками, должны находиться в разных группах. Если это невозможно, граф не является двудольным.

Группы студентов:
Массив groups хранит группу каждого студента (0 или 1).
Если соседний студент уже находится в той же группе, что и текущий, это нарушение условия задачи.

Результат:
Если для любой компоненты графа BFS обнаружит нарушение, выводится NO.
Если все компоненты графа можно разбить на две группы, выводится YES.

Автор решения задачи: hdhai.com