Pinely Round 1 (Div. 1 + Div. 2) |
---|
Закончено |
Вам дан простой неориентированный граф, состоящий из $$$n$$$ вершин. Граф не содержит петель, между каждой парой вершин существует не более одного ребра. Ваша задача проста: сделать граф связным.
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Найдите минимальное количество операций, необходимых для того, чтобы сделать граф связным. Также найдите любую последовательность операций минимальной длины, которая делает граф связным.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 800$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 4000$$$) — количество вершин в графе.
Затем следуют $$$n$$$ строк. В $$$i$$$-й строке содержится бинарная строка $$$s_i$$$ длины $$$n$$$, где $$$s_{i,j}$$$ равно '1', если между вершинами $$$i$$$ и $$$j$$$ изначально существует ребро, иначе $$$s_{i,j}$$$ равно '0'.
Гарантируется, что $$$s_{i,i}$$$ всегда '0' и $$$s_{i,j}=s_{j,i}$$$ для $$$1\leq i,j\leq n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$4000$$$.
Для каждого набора входных данных в первой строке выведите целое число $$$m$$$ — минимально необходимое количество операций.
Если $$$m$$$ больше нуля, то выведите дополнительную строку, состоящую из $$$m$$$ целых чисел — вершин, выбранных в операциях в вашем решении. Если существует несколько решений с минимальным количеством операций, выведите любое из них.
430111001003000001010401001000000100106001100000011100100101000010001010010
0 1 1 2 3 4 3 2 5 6
В первом наборе входных данных граф связен в начале, поэтому ответ — $$$0$$$.
Во втором наборе входных данных, если мы выполним операцию с вершиной $$$1$$$, то получим следующий граф, представленный следующей матрицей смежности:
$$$$$$ \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix} $$$$$$
Очевидно, что приведенный выше граф является связным.
В третьем наборе входных данных, если мы проделаем операцию с вершинами $$$3$$$ и $$$4$$$, то получим следующий граф, представленный следующей матрицей смежности:
$$$$$$ \begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix} $$$$$$
Очевидно, что приведенный выше граф является связным, и можно доказать, что мы не можем выполнить менее $$$2$$$ операций, чтобы сделать граф связным.
Название |
---|