Задача Chain

Задача Chain

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

Технічні умови. Ви вводите з клавіатури число N (2<=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

 

 

© LIKT 1998-2018