e-olymp
Məsələlər

Поиск гамильтонова цикла в условиях т-мы Хватала

Поиск гамильтонова цикла в условиях т-мы Хватала

Дан граф из N вершин, для которого выполняется условие теоремы Хватала, то есть, в отсортированной последовательности его степеней вершин dk для любого k < n/2 верно либо dk > k, либо dn - kn-k. Ваша задача - найти гамильтонов цикл.

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

На первой строке входного файла записано целое число N (3N100) - количество вершин в графе. На следующих N строках записана матрица смежности. Т.к. матрица смежности симметрична, а на диагонали всегда стоят нули, на i-й строке записаны i-1 символ - нули и единицы. Если j-й символ i-й строки равен единице, значит есть ребро между вершинами i и j.

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

Выведите перестановку из N чисел - номера вершин в порядке гамильтонова цикла.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
4
1
11
101
Çıxış verilənləri
1 2 3 4
Теорема Брукса как-нибудь