Неверный ответ — задача "Чемпионат Урала"

Question

Задача:

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

Исходные данные:

В первой строке даны 2 числа: N, количество задач на туре, и M, количество пар задач, которые недопустимо давать на одном туре (1 ≤ N ≤ 50; 0 ≤ M ≤ 100). Далее следуют M строк по 2 числа в каждой — номера схожих задач.

Результат:

Выведите 2 строки, в каждой по N чисел — номера задач на каждый тур. Если решения нет, выведите «IMPOSSIBLE». Если задача имеет несколько решений, можно вывести любое.

Пример:

Исходные данные:

Результат:

1 4
2 3

Мой код:

def dfs(k, t):
    global b, c, f, n
    b[k] = t
    c[t] += 1
    for i in range(n):
        if a[k][i]:
            if b[i] == -1:
                dfs(i, 1 - t)
            elif b[i] == b[k]:
                f[0] = 1

n, m = map(int, input().split())
n *= 2
a = [[0 for _ in range(n)] for _ in range(n)]
b = [-1 for _ in range(n)]
c = [0, 0]
f = [0]

for _ in range(m):
    fir, sec = map(int, input().split())
    fir -= 1
    sec -= 1
    a[fir][sec] = a[sec][fir] = 1  

for i in range(n):
    if b[i] == -1:
        dfs(i, 0)

if f[0] or c[0] != c[1]:
    print("IMPOSSIBLE")
else:
    tour1 = [i + 1 for i in range(n) if b[i] == 0]
    tour2 = [i + 1 for i in range(n) if b[i] == 1]
    print(" ".join(map(str, tour1)))
    print(" ".join(map(str, tour2)))

Почему пишет, что ответ неверный?

Answer 1

Вы задаёте единицами запрещённые рёбра, а работаете при раскраске с матрицей a, как будто единицы - разрешённые рёбра. Изменённая часть:

a = [[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    a[i][i]=0
b = [-1 for _ in range(n)]
c = [0, 0]
f = [0]

for _ in range(m):
    fir, sec = map(int, input().split())
    fir -= 1
    sec -= 1
    a[fir][sec] = 0
    a[sec][fir] = 0

БЛОГ НА HUSL

Неверный ответ — задача "Чемпионат Урала"

Ответы (1 шт):