Задача 15: Банкет

Условие задачи:

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

Входные данные:

В первой строке входных данных содержатся два числа: \(N\) и \(M\) \((1 <= N,M <= 100)\), где \(N\) – количество ОВП, а \(M\) – количество пар ОВП, которые не могут сидеть за одним столом. В следующих \(M\) строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

Выходные данные:

Если способ рассадить ОВП существует, то выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Решение:

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())

v = [[int(i) for i in input().split()] for _ in range(m)]

used = [0 for _ in range(n)]
g = [[] for i in range(n)]
for i in v:
    g[i[0] - 1].append(i[1] - 1)
    g[i[1] - 1].append(i[0] - 1)


def dfs(v, n):
    global used, vsv
    if used[v] == 0:
        used[v] = n
        n %= 2
        n += 1
        aaa = [True]
        for i in g[v]:
            aaa.append(dfs(i, n))
        return all(aaa)
    else:
        return used[v] == n

ok = True
for i in range(n):
    if not used[i]:
        if not dfs(i, 1):
            ok = False

if ok:
    print("YES")
    for i in range(n):
        if used[i] == 1:
            print(i + 1, end=" ")
    print()
else:
    print("NO")

Задача 15: Банкет

Условие задачи:

Входные данные:

Выходные данные:

Решение:

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик

Пожалуйста, подождите загрузки решения