Изменения

bool used[]; int tin[]; int up[]; bool В массиве <tex>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 int <tex>time \leftarrow time + 1</tex> <tex>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 ++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; }