Задачи
Гамильтонов цикл в полном графе
Гамильтонов цикл в полном графе
Дан граф из N вершин, в котором степень любой вершины не меньше N/2. Ваша задача - найти гамильтонов цикл.
Входные данные
На первой строке входного файла записано целое число N (3 ≤ N ≤ 4000) - количество вершин в графе. На следующих N строках записана матрица смежности. Т.к. матрица смежности симметрична, а на диагонали всегда стоят нули, на i-й строке записаны i-1 символ - нули и единицы. Если j-й символ i-й строки равен единице, значит есть ребро между вершинами i и j.
Гарантируется, что в графе есть гамильтонов цикл и что степень каждой вершины не меньше N/2.
Выходные данные
Выведите перестановку из N чисел - номера вершин в порядке гамильтонова цикла.
Пример
Входные данные #1
4 1 11 101
Выходные данные #1
1 2 3 4