Блог пользователя CrazzyBeer

Автор CrazzyBeer, 9 лет назад, По-русски

Здравствуйте.

Вопрос такой. Имеется неориентированный граф V. Известно, что из любой вершины графа u можно попасть в любую вершину v.

Важной вершиной называют такую вершину, при удалении которой и всех её рёбер — некоторая вершина u теряет связь с некоторой вершиной v.

Требуется найти количество важных вершин.

В голову сразу лезет поиск в глубину, но он мне, почему-то, кажется слишком громоздким. Есть ли какой-то более легкий метод или алгоритм?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Такая вершина называется точкой сочленения, вот тут можно почитать:
http://e-maxx.ru/algo/cutpoints
А вот тут посмотреть:
http://sis.khashaev.ru/2008/august/b-prime/aZgdH1KVnhw/

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This is just the number of critical vertexes in a graph. The idea is to use Trajan's algorithm.