1190: Ланцюг -> Перемоги вихідного дня 2


Submit solution


Points:10
Time limit:0.1s
Python1.0s
Memory limit:64M
Python250M
Author:

Problem type

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

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

У стандартному потоці міститься число N<=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.