Олимпиадный тренинг

Задача . B. Найдите перестановку

Задача

Темы: графы Перебор поиск в глубину и подобное реализация сортировки *1300

Вам дан неориентированный граф с $n$ вершинами, пронумерованными от $1$ до $n$. Этот граф кодирует секретную перестановку$^{\text{∗}}$ $p$ длины $n$. Граф строится следующим образом:

Для каждой пары целых чисел $1 \le i < j \le n$, между вершиной $p_i$ и вершиной $p_j$ добавляется неориентированное ребро тогда и только тогда, когда $p_i < p_j$. Обратите внимание, что ребро добавляется не между вершинами $i$ и $j$, а между вершинами соответствующих им элементов. Обратитесь к примечаниям для лучшего понимания.

Ваша задача состоит в том, чтобы восстановить и вывести перестановку $p$. Можно доказать, что перестановка $p$ может быть определена однозначно.

$^{\text{∗}}$Перестановкой длины $n$ является массив, состоящий из $n$ различных целых чисел от $1$ до $n$ в произвольном порядке. Например, $[2,3,1,5,4]$ — перестановка, но $[1,2,2]$ не перестановка ($2$ встречается в массиве дважды) и $[1,3,4]$ тоже не перестановка ($n=3$, но в массиве встречается $4$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $t$ ($1 \le t \le 500$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $n$ ($1 \le n \le 1000$).

В $i$-й из следующих $n$ строк содержится $n$ символов $g_{i, 1}g_{i, 2}\ldots g_{i, n}$ ($g_{i, j} = \mathtt{0}$ или $g_{i, j} = \mathtt{1}$) — матрица смежности. $g_{i, j} = \mathtt{1}$ тогда и только тогда, когда существует ребро между вершинами $i$ и $j$.

Гарантируется, что существует перестановка $p$, которая генерирует данный граф. Также гарантируется, что граф неориентирован и не имеет петель, то есть выполняется $g_{i, j} = g_{j, i}$ и $g_{i, i} = \mathtt{0}$.

Гарантируется, что сумма значений $n$ по всем наборам входных данных не превосходит $1000$.

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

Для каждого набора входных данных выведите $n$ целых чисел $p_1, p_2, \ldots, p_n$ — восстановленную перестановку.

Примечание

В первом наборе входных данных $p = [1]$. Поскольку нет пар $1 \le i < j \le n$, в графе нет рёбер.

Граф для второго набора входных данных показан ниже. Например, когда мы выбираем $i = 3$ и $j = 4$, мы добавляем ребро между вершинами $p_i = 1$ и $p_j = 3$, потому что $p_i < p_j$. Однако, когда мы выбираем $i = 2$ и $j = 3$, то $p_i = 2$ и $p_j = 1$, так что $p_i < p_j$ не выполняется. Поэтому мы не добавляем ребро между $2$ и $1$.

$\text{[math]}$

В третьем наборе входных данных в графе нет рёбер, поэтому нет пар целых чисел $1 \le i < j \le n$ таких, что $p_i < p_j$. Следовательно, $p = [6, 5, 4, 3, 2, 1]$.

Примеры

№	Входные данные	Выходные данные
1	3 1 0 5 00101 00101 11001 00001 11110 6 000000 000000 000000 000000 000000 000000	1 4 2 1 3 5 6 5 4 3 2 1

time 1500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет