Наибольшее паросочетание в двудольном графе
Графы
Экстремальная
Есть n_left вершин слева и n_right вершин справа, список edges допустимых пар [левая, правая]. Верните максимальное число пар, которые можно соединить так, чтобы каждая вершина участвовала не более чем в одной паре (алгоритм Куна: поиск увеличивающих путей).
Сигнатура функции
max_bipartite_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]] | 3 |
| [2, 2, [[0, 0], [1, 0]]] | 1 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →