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

Прежде всего, чтобы найти узел, который не нужен для того, чтобы сделать граф связным, вам нужно найти цикл. Как только вы найдете цикл, вы поймете, что все эти ребра в этом цикле не нужны. Все оставшиеся ребра в графе необходимы, чтобы удерживать граф вместе, поэтому вы выполняете простой обход графа и подсчитываете количество связанных вершин, чтобы найти минимальное количество узлов, которые нужно удалить, чтобы сделать граф несвязным. Я не уверен, что это самый эффективный способ, просто самый эффективный в моей голове. Если V — количество вершин, а E — количество ребер, временная сложность будет где-то около O(V + E) + O(V), поскольку начальное нахождение цикла равно O(V + E), а подсчет узлы - O (V). Поскольку E >= V, временная сложность может быть округлена до O(E), но с огромными постоянными множителями.

Считайте граф неориентированным.

totalDegree = sum of degree of all nodes.
while(totalDegree > 0) {
    Remove the node with highest degree and it's edges.
    Update degree count of each node.
    totalDegree = sum of degree of all remaining nodes.
}
remaining nodes are all disconnected

Попытка подумать о случае, когда он не даст минимального количества узлов.