Здравствуйте.
Вопрос такой. Имеется неориентированный граф V. Известно, что из любой вершины графа u можно попасть в любую вершину v.
Важной вершиной называют такую вершину, при удалении которой и всех её рёбер — некоторая вершина u теряет связь с некоторой вершиной v.
Требуется найти количество важных вершин.
В голову сразу лезет поиск в глубину, но он мне, почему-то, кажется слишком громоздким. Есть ли какой-то более легкий метод или алгоритм?
Такая вершина называется точкой сочленения, вот тут можно почитать:
http://e-maxx.ru/algo/cutpoints
А вот тут посмотреть:
http://sis.khashaev.ru/2008/august/b-prime/aZgdH1KVnhw/
Поиск точек сочленения
This is just the number of critical vertexes in a graph. The idea is to use Trajan's algorithm.
Here is a link to Geek for Geeks tutorial about that.
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/