Как исправить ошибку. Необходимо находить мосты в графе. Реализация алгоритма
Решаю задачу на поиск мостов в неориентированном графе с возможными кратными ребрами и петлями. Необходимо посчитать и вывести количество мостов а также номера соответсвующих ребер в графе.
При рукписном тесте выдает ошибку
input:
1 2
2 1
ожидаемый output: 0 полученный output: 1 2 (1 - количество мостов, 2 - номер ребра, которое является мостом (порядок как в input)
Алгоритм:
void DFS(int* checkedVert, int* h, int* low, int* bridge, int* countBridge, int v, int p, struct Adjacency* graph) {
checkedVert[v] = 1;
if (p == -1) {
h[v] = 0;
low[v] = 0;
} else {
h[v] = h[p] + 1;
low[v] = h[p] + 1;
}
struct NodeGraph* Node = graph[v].head;
while (Node != NULL) {
if (Node->vert != p) {
if (checkedVert[Node->vert]) {
// если ребро обратное
low[v] = myMin(low[v], h[Node->vert]);
} else {
// если ребро прямое
DFS(checkedVert, h, low, bridge, countBridge, Node->vert, v, graph);
low[v] = myMin(low[v], low[Node->vert]);
if (h[v] < low[Node->vert]) {
//printf("%d %d\n", v, Node->vert);
bridge[(*countBridge)++] = Node->numb;
}
}
}
Node = Node->next;
}
}
В одной учебной методичке с представленным алгоритмом нашел следующее:
"Если в графе могут быть кратные рёбра, необходимо запоминать не родителя вершины, а идентификатор ребра, по которому мы пришли в вершину, и пропускать в цикле только это ребро".
граф храню списком смежности:
struct NodeGraph {
int vert;
int numb;
struct NodeGraph* next;
};
struct Adjacency {
struct NodeGraph* head;
};