Изменения

В массиве <tex> bool used[]; int tin[]; int up[]; bool answer[]<; //tex> для каждой вершины содержится булево значение - является она точкой сочленения или нет. Изначально изначально все значения '''false'''. int time; '''void dfs'''<tex>(int u, \, int prev)</tex> { <tex>used[u] \leftarrow</tex>'''= true'''; <tex>tin[u] \leftarrow time</tex> //задание времени входа в вершину u <tex>= up[u] \leftarrow = time</tex> ++; //задание времени входа tin и начального значения up для вершины u <tex>time \leftarrow time + 1</tex> <tex>int count \leftarrow = 0</tex> ; //счетчик количества детей вершины u в дереве обхода '''for '''<tex>(v : uv \in из E)</tex> { '''if '''<tex>(v == prev</tex>) '''continue'''; '''if '''<tex>(used[v]</tex> ) //v - предок вершины u, uv - обратное ребро <tex>up[u] \leftarrow = min(up[u], \, tin[v])</tex>; '''else''' //v - ребенок вершины u { <tex>++count \leftarrow count + 1</tex>; '''dfs'''<tex>(v, u)</tex>; <tex>up[u] \leftarrow = min(up[u], \, up[v])</tex>; '''if '''<tex>(up[v] \ge >= tin[u]</tex>) <tex>answer[u] \leftarrow</tex>'''= true''' ; //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения } } '''if '''<tex>(p == -1</tex> ) //является ли u корнем дерева обхода <tex>answer[u] \leftarrow = (count > 1)</tex>; //проверка количества детей у корня дерева } int main() { ... //инициализация графа, выбор корня дерева обхода root time = 0; dfs(root, -1); return 0; }Для поиска точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом: int main() { ... for (root из V) if (!used[root]) { time = 0; dfs(root, -1); } return 0; }

[http://eАсанов М., Баранский В., Расин В. -maxx.ru/algo/ MAXimalДискретная математика:Графы, матроиды, алгоритмы — Ижевск:algo]ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.