Я знаю, что мы можем эффективно найти все точки сочленения в графе, используя DFS. 1
Но что, если не все узлы должны быть соединены, а вместо этого у нас есть набор пар узлов, которые должны взаимодействовать (между ними есть путь). Как эффективно найти все узлы (вершины), удаление которых приведет к отключению некоторых из упомянутых пар (не могут общаться друг с другом)?
Например, у нас могут быть разные случаи для изображения ниже:
- Если парами являются AB и C -D, то 2 не является разрезом вершины, потому что пары остаются соединенными.
- Если парами являются A- C и BD, то 2 обрезается по вершине, потому что пары не могут общаться (между ними нет пути).
Если мы знаем набор пар, которым нужно общаться, какой самый эффективный способ найти все "срезы вершин"?
