can_divide_students

#ChatGPT
(код не проверялся, а напрямую скопирован из диалога с ChatGPT в качестве примера)

'''
Ниже представлен код на Python для решения задачи о разделении группы студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы:
'''

from collections import defaultdict
from queue import Queue

def can_divide_students(n, pairs):
    # n - общее количество студентов
    # pairs - список пар студентов, которые обменивались записками

    # создаем пустой граф с двумя долями
    graph = defaultdict(list)
    source = 0
    sink = n + 1

    # добавляем ребра в граф
    for i in range(1, n+1):
        if i in pairs:
            for j in pairs[i]:
                graph[i].append(j)
                graph[j].append(i)
        else:
            graph[source].append(i)
            graph[i].append(source)

            graph[i].append(sink)
            graph[sink].append(i)

    # запускаем поиск максимального потока в графе
    max_flow = 0
    while True:
        visited = [False] * (n + 2)
        q = Queue()
        q.put(source)
        visited[source] = True
        parent = defaultdict(int)

        while not q.empty():
            u = q.get()
            for v in graph[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[v] = u
                    q.put(v)

                    if v == sink:
                        path_flow = float("Inf")
                        s = sink
                        while s != source:
                            path_flow = min(path_flow, 1)
                            s = parent[s]

                        max_flow += path_flow
                        u = sink
                        while u != source:
                            prev = parent[u]
                            graph[prev].remove(u)
                            graph[u].append(prev)
                            u = prev

                        break

        if not visited[sink]:
            break

    # если максимальный поток равен количеству обменов записками,
    # то студенты могут быть разделены на две группы
    if max_flow == len(pairs):
        return True
    else:
        return False


pairs = {1: [2, 3], 2: [3], 4: [3, 5]}
n = 5
print(can_divide_students(n, pairs)) # True

'''
В данном примере группа студентов состоит из 5 человек, и некоторые студенты обменивались записками (1 обмен между студентами 1 и 2, 1 обмен между студентами 1 и 3, и 2 обмена между студентами 3 и 4). Функция can_divide_students возвращает True, что означает, что студенты могут быть разделены на две группы в соответствии с требованиями задачи.

'''