You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Problem:
If there is double edge between two nodes, due to if (to == p) continue;, the edge (v-to) will be considered as a bridge, which is not correct.
Here is the modified code.
introduce a new variable called parentSkipped inside the dfs()
bool parentSkipped = false;
instead of just if (to == p) continue; do the following
if (to == p && !parentSkipped) {
parentSkipped = true;
continue;
}
The text was updated successfully, but these errors were encountered:
SubhramRanaRZP
changed the title
The following scenario will results in wrong answer
BUG : bridge finding algorithm offline
Nov 15, 2022
Article: Finding Bridges in O(N+M)
Problem:
If there is double edge between two nodes, due to
if (to == p) continue;
, the edge (v-to) will be considered as a bridge, which is not correct.Here is the modified code.
parentSkipped
inside thedfs()
bool parentSkipped = false;
if (to == p) continue;
do the followingif (to == p && !parentSkipped) {
parentSkipped = true;
continue;
}
The text was updated successfully, but these errors were encountered: