В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.
Входные данные
В первой строке заданы два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.
Выходные данные
Выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.
Пример
INPUT.TXT
OUTPUT.TXT
3 1
0 1 0
1 0 1
0 1 0
2
Ответы
Ответ:
Для решения этой задачи можно воспользоваться транзитивным замыканием матрицы смежности. Ваш запрос подразумевает поиск количества гарантированных друзей у конкретного человека с учетом транзитивности дружбы. Ниже приведен пример кода на Python, который решает данную задачу:
```python
def transitive_closure(graph):
n = len(graph)
closure = [row[:] for row in graph]
for k in range(n):
for i in range(n):
for j in range(n):
closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])
return closure
def count_friends(graph, person):
closure = transitive_closure(graph)
friends_count = sum(closure[person-1])
return friends_count - 1 # Exclude the person itself
# Чтение входных данных
n, s = map(int, input().split())
adj_matrix = [list(map(int, input().split())) for _ in range(n)]
# Получение ответа и вывод
result = count_friends(adj_matrix, s)
print(result)
```
Данный код сначала создает транзитивное замыкание матрицы смежности, а затем считает количество гарантированных друзей у заданного человека. В данном примере он считает, что нумерация людей начинается с 1, поэтому в ответе вычитается 1, чтобы не учитывать самого человека в подсчете друзей.