1190: Ланцюг


Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

\(N\) кілець зчеплені між собою. Яку мінімальну кількість кілець слід вилучити, щоб утворився ланцюг? Кільця задаються матрицею \(A(N\) x \(N)\). \(А(i,j) = 1\), якщо \(i\) та \(j\) кільця зчеплені між собою та \(А(i,j)=0\), якщо ні.

Формат вихідних даних

У стандартному потоці міститься число \(N\) \((1 \le N \le 50)\) кількість вершин, а потім в \(N\) стрічках по \(N\) нулів чи одиниць через пропуск.

Формат вихідних даних

У стандартний потік вивести єдине шукане число – мінімальна кількість вилучених кілець.

Приклад вхідних даних

5
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0

Приклад вихідних даних

1

Comments

There are no comments at the moment.