Детектив: ключевой свидетель
Матрицы
Сложная
На месте преступления было n человек. Матрица knows: knows[i][j] = 1, если человек i знает человека j. Ключевой свидетель - тот, кого знают все остальные, а он не знает никого. Верните его номер или -1, если такого нет. Классика: наивно это O(n^2) проверок, но кандидата можно найти за один проход.
Сигнатура функции
find_celebrity_witness(knows: list[list[int]]) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[[0, 1, 0], [0, 0, 0], [0, 1, 0]]] | 1 |
| [[[0, 1], [0, 0]]] | 1 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →