Здравствуйте, Николаев Александр Валерьевич!

Прямое ребро (x,y) является мостом если и только если low[y]=enter[y]. (Обратное ребро никогда не может быть мостом). Вершина x является точкой сочленения если low[x] = enter[x], за исключением случая когда она - корень дерева поиска и имеет менее чем двух потомков в дереве.

После небольших изменений программа вычисляет и точки сочленения.



Приложение:
/*
* Поиск мостов и двусвязных компонент.
* Даниил Швед, 2008. МФТИ.
* danshved [no-spam] gmail.com
*/
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <conio.h>
using namespace std;

typedef vector<int> VInt;
typedef vector<VInt> VVInt;
typedef VInt::iterator VIter;
typedef pair<int, int> PInt;
typedef vector<PInt> VPInt;
typedef vector<VPInt> VVPInt;
typedef VPInt::iterator VPIter;

VVInt graph;
VInt colors, parents, enter, leave, low, bcc;
int myTime = 0;
int newIndex = 0;


/*
* Поиск в глубину, выполняющий вычисление enter, leave и low
*/
void visitLow(int u) {
colors[u] = 1;
low[u] = enter[u] = ++myTime;
printf("visitLow(%d)\n",u);
for(VIter it = graph[u].begin(); it != graph[u].end(); it++)//проходим по всем вершинам, связанным с текущей
if(colors[*it] == 0) {
parents[*it] = u;
printf("parents[%d]=%d\n",*it,u);
visitLow(*it);
low[u] = min(low[u], low[*it]);
printf("low[%d]=%d\n",u,low[u]);
} else if(colors[*it] == 1 && *it != parents[u]) {
low[u] = min(low[u], enter[*it]);
printf("low[%d]=%d\n",u,low[u]);
}

colors[u] = 2;
leave[u] = ++myTime;
printf("enter[%d]=%d\n",u,enter[u]);
}

/*
* Второй поиск в глубину, присвающий идентификаторы bcc
*/
void visitBCC(int u) {
for(VIter it = graph[u].begin(); it != graph[u].end(); it++)
if(parents[*it] == u) {
bcc[*it] = (low[*it] < enter[u]) ? bcc[u] : // Дочернее ребро эквивалентно текущему
(low[*it] > enter[u]) ? -1 : // Дочернее ребро есть мост
(newIndex++); // Дочернее ребро лежит в новой компоненте
visitBCC(*it);
}
}

/*
* Получение номера BCC, которому принадлежит ребро, или -1, если это мост
* (u, v) действительно должно быть ребром, иначе возвращенный результат не имеет смысла
*/
int getBCC(int u, int v) {
return bcc[(enter[u] > enter[v]) ? u : v];
}

/*
* На входе: числа n и m, затем m описаний ребер
* На выходе: список мостов, затем списки ребер в каждой компоненте
*/
int main() {
int n, m, i;

FILE *input= fopen("input.txt", "r+");
// Прочитаем граф
fscanf(input,"%d%d", &n, &m);
graph.resize(n);
while(m--) {
int from, to;
fscanf(input,"%d%d", &from, &to);
graph[from].push_back(to);
graph[to].push_back(from);
}

// Запустим первый поиск (вычислим enter и low)
colors.assign(n, 0);
parents.assign(n, -1);
enter.resize(n);
leave.resize(n);
low.resize(n);
for(i = 0; i < n; i++)
if(colors[i] == 0)
visitLow(i);



// Запустим второй поиск (определение идентификаторов bcc)
// Второй поиск запускается "по следам" первого,
// то есть проходит по уже найденному дереву
bcc.assign(n, -1);
for(i = 0; i < n; i++)
if(parents[i] == -1)
visitBCC(i);

if(graph[0].size()>1)
printf("Tochka sochleneniya %d ee vremya dostupa %d",0,low[i]);
for(i = 1; i < n; i++)
{
//if(low[i]==enter[i])
if(bcc[i]==-1)
printf("Tochka sochleneniya %d ee vremya dostupa %d",i,low[i]);
}
// Выведем результат
VPInt bridges;
VVPInt comps(newIndex);
for(i = 0; i < n; i++)
for(VIter it = graph[i].begin(); it != graph[i].end(); it++)
if(i < *it) {
int id = getBCC(i, *it);
((id == -1) ? bridges : comps[id]).push_back(PInt(i, *it));
}

printf("Bridges: ");
for(VPIter bridge = bridges.begin(); bridge != bridges.end(); bridge++)
printf("(%d, %d) ", bridge->first, bridge->second);
printf("\n");

for(i = 0; i < newIndex; i++) {
printf("Component %d: ", i);
for(VPIter edge = comps[i].begin(); edge != comps[i].end(); edge++)
printf("(%d, %d) ", edge->first, edge->second);
printf("\n");
}
getch();
}