Məsələlər
Гамильтонов цикл в полном графе
Гамильтонов цикл в полном графе
Дан граф из \textbf{N} вершин, в котором степень любой вершины не меньше \textbf{N/2}. Ваша задача - найти гамильтонов цикл.
\InputFile
На первой строке входного файла записано целое число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{4000}) - количество вершин в графе. На следующих \textbf{N} строках записана матрица смежности. Т.к. матрица смежности симметрична, а на диагонали всегда стоят нули, на \textbf{i}-й строке записаны \textbf{i-1} символ - нули и единицы. Если \textbf{j}-й символ \textbf{i}-й строки равен единице, значит есть ребро между вершинами \textbf{i} и \textbf{j}.
Гарантируется, что в графе есть гамильтонов цикл и что степень каждой вершины не меньше \textbf{N/2}.
\OutputFile
Выведите перестановку из \textbf{N} чисел - номера вершин в порядке гамильтонова цикла.
Giriş verilənləri #1
4 1 11 101
Çıxış verilənləri #1
1 2 3 4