Intern

9. Nusxa olish Imtihonda, professor Floyd ba'zi talabalar notalarni almashayotganini payqab qoldi. Dastlab, ularni hammasiga 2 baho qo'yishni istagan, ammo professor mehribon bo'lib, talabalarni ikki guruhga bo'lishga qaror qilgan: nusxa olishga ruxsat beradiganlar va faqat birinchi guruhga 2 baho qo'yadiganlar. Professor barcha talabalar o'rtasida notalarni almashgan juftliklarni yozib olgan. Talabalarni ikki guruhga bo'lish mumkinligini aniqlash kerak, shunda har qanday notalarni almashish bir guruhdagi talaba tomonidan ikkinchi guruhdagi talaba bilan amalga oshiriladi. Kiritish formati Birinchi satrda ikkita raqam N va M joylashgan — talabalar soni va notalarni almashgan talabalar juftliklari soni (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Keyingi M satrda, talabalar juftliklari tavsifi berilgan: notalarni almashgan talabalar raqamlari (talaba raqamlash 1 dan boshlanadi, har bir juftlik bir marta ko'rsatilgan). Chiqish formati Professor Floydning vazifasiga javob yozilishi kerak. Talabalarni ikki guruhga bo'lish mumkin bo'lsa, YES yozing; aks holda, NO.

sobes.tech AI

AIdan javob

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

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

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

Oldingi Keyingi