fix bug in bridge searching offline algorithm in case of duplicate edges

NaimSS · NaimSS · commit 115e2b203f6d · 2024-05-04T11:10:05.000+02:00
diff --git a/src/graph/bridge-searching.md b/src/graph/bridge-searching.md
@@ -40,7 +40,10 @@ The implementation needs to distinguish three cases: when we go down the edge in
 
 To implement this, we need a depth first search function which accepts the parent vertex of the current node.
 
-```cpp
+For the cases of multiple edges, we need to be careful when ignoring the edge from the parent. To solve this issue, we can add a flag `parent_skipped` which will ensure we only skip the parent once.
+
+```{.cpp file=bridge_searching_offline}
+void IS_BRIDGE(int v,int to); // some function to process the found bridge
 int n; // number of nodes
 vector<vector<int>> adj; // adjacency list of graph
 
@@ -51,8 +54,12 @@ int timer;
 void dfs(int v, int p = -1) {
     visited[v] = true;
     tin[v] = low[v] = timer++;
+    bool parent_skipped = false;
     for (int to : adj[v]) {
-        if (to == p) continue;
+        if (to == p && !parent_skipped) {
+            parent_skipped = true;
+            continue;
+        }
         if (visited[to]) {
             low[v] = min(low[v], tin[to]);
         } else {
diff --git a/test/test_bridge_searching_offline.cpp b/test/test_bridge_searching_offline.cpp
@@ -0,0 +1,48 @@
+#include <cassert>
+#include <vector>
+#include <set>
+using namespace std;
+
+#include "bridge_searching_offline.h"
+
+vector<pair<int,int>> bridges;
+void IS_BRIDGE(int v,int to){
+    bridges.push_back({v, to});
+}
+
+void normalize(vector<pair<int,int>> &v){
+    for(auto &p : v){
+        if(p.first > p.second)swap(p.first, p.second);
+    }
+    sort(v.begin(), v.end());
+}
+
+void test_suite(
+    int _n,
+    vector<vector<int>> _adj,
+    vector<pair<int,int> > expected_bridges){
+    bridges.clear();
+    n = _n;
+    adj = _adj;
+    find_bridges();
+    normalize(&expected_bridges);
+    normalize(&bridges);
+    assert(bridges == expected_bridges);
+}
+
+int main() {
+    {
+        int n = 5;
+        vector<vector<int>> adj(n);
+        adj[0].push_back(1), adj[1].push_back(0);
+        adj[0].push_back(1), adj[1].push_back(0);
+        
+        adj[2].push_back(3), adj[3].push_back(2);
+        adj[3].push_back(4), adj[4].push_back(3);
+        vector<pair<int,int> > expected_bridges;
+        expected_bridges.push_back({2,3});
+        expected_bridges.push_back({3,4});
+        // note that 0-1 is not a bridge due to duplicate edges!
+        test_suite(n, adj, expected_bridges);
+    }
+}
