Кіріспе формат Бірінші жолда студенттердің саны N және ноталар алмасқан жұптардың саны M көрсетіледі (1 ≤ N ≤ 10^2, 0 ≤ M ≤ N(N-1)/2). Келесі M жолда ноталар алмасқан студенттердің жұптарының сипаттамалары беріледі: екі сан, ноталар алмасқан студенттердің нөмірлері (студенттердің нөмірі 1-ден басталады, әр жұп бір реттен артық көрсетілмеген). Шығыс формат Профессор Флойдтың тапсырмасына жауап беру керек. Егер студенттерді екі топқа бөлу мүмкін болса - YES, ал болмаса - NO.

Міндет студенттерді екі топқа бөлуге болатынын тексеруге байланысты, яғни барлық хат алмасу жұптары әртүрлі топтағы студенттер арасында бола ма, жоқ па. Бұл графтың екі түсті болуын тексеру классикалық тапсырмасы.

Шешім алгоритмі:

1. Студенттерді графтың төбелері ретінде көрсету, ал хат алмасу жұптарын рёбер ретінде белгілеу.
2. Графты екі түске (мысалы, 0 және 1) бояуға тырысу, осылайша көрші төбелер әртүрлі түсте болатындай.
3. Егер графты обход кезінде (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")

Егер шығу "ИӘ" болса, профессор студенттерді екі топқа бөле алады, ал егер жоқ болса — бөле алмайды.