Максимизируйте количество ребер, чтобы вырезать в связанном графе

Question

Этот вопрос очень похож на Критические соединения Leetcode в сети . Учитывая неориентированный граф, мы хотим найти все мосты. Ребро в неориентированном связанном графе - это мост , если его удаление отключает график.

Вариант

Вместо того, чтобы найти все мосты, я хочу увеличить количество ребер, которые нужно удалить, чтобы график оставался связанным.

Пример 1

Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]

Output: 1

Во-первых, я могу удалить [3,4], [1,3] или [1,4]. Затем, после удаления любого из 3 ребер, оставшиеся ребра являются мостами. Следовательно, максимальное количество ребер, которые нужно удалить, чтобы график оставался подключенным, составляет 1.

Пример 2

Input: n = 6, edges = [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [4, 6], [5, 6]]

Output: 2

Answer 1

Ну, это легко, если у нас есть E ребер и N узлов в связанном графе, мы можем удалить E-N+1 ребер, чтобы граф остался связанным.

Как это сделать?:

Просто выполните DFS / BFS, чтобы найти любое связующее дерево графа, поскольку связующее дерево связано, мы можем просто удалить все остальные ребра.