Bridges Search Algorithm
The Bridges Search Algorithm is a graph traversal technique used to find and identify all the bridges in a given undirected graph. A bridge in a graph is an edge whose removal increases the number of connected components, or in simpler terms, disconnects the graph. These bridges are crucial in understanding the structure of the graph, as they represent weak points and bottlenecks in networks such as communication networks or transport systems. The algorithm is based on the depth-first search (DFS) technique and is used to identify these bridges efficiently.
The Bridges Search Algorithm starts by visiting an arbitrary node in the graph and then proceeds with a depth-first search traversal. During the traversal, the algorithm maintains two values for each node: the discovery time and the low value. The discovery time is the order in which the nodes are visited, while the low value is the smallest discovery time reachable from the current node. When the DFS returns from a subtree, the algorithm updates the low value of the parent node with the minimum low value of its children. If the low value of a child node is greater than the discovery time of the parent node, then the edge between the parent and child nodes is identified as a bridge. By systematically visiting all nodes in the graph and applying this logic, the Bridges Search Algorithm effectively detects all bridges present in the graph.
/**************************************************************************************
Algorithm for finding all bridges in the graph (edges, after removal of
which graph divides into several components). O(M)
Based on problem C from here: http://codeforces.ru/gym/100083
**************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 105000;
int n, m;
vector <int> g[MAXN];
vector <int> ind[MAXN];
int tin[MAXN], mn[MAXN];
bool used[MAXN];
vector <int> bridges;
int timer;
void dfs(int v, int par = -1) {
used[v] = true;
timer++;
tin[v] = timer;
mn[v] = tin[v];
for (int i = 0; i < (int) g[v].size(); i++) {
int to = g[v][i];
if (!used[to]) {
dfs(to, v);
if (mn[to] == tin[to]) {
bridges.push_back(ind[v][i]);
}
mn[v] = min(mn[v], mn[to]);
}
else if (to != par) {
mn[v] = min(mn[v], mn[to]);
}
}
}
int main() {
assert(freopen("bridges.in","r",stdin));
assert(freopen("bridges.out","w",stdout));
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int from, to;
scanf("%d %d", &from, &to);
g[from].push_back(to);
ind[from].push_back(i);
g[to].push_back(from);
ind[to].push_back(i);
}
for (int i = 1; i <= n; i++)
if (!used[i])
dfs(i);
sort(bridges.begin(), bridges.end());
printf("%d\n", (int) bridges.size());
for (int i = 0; i < (int) bridges.size(); i++)
printf("%d\n", bridges[i]);
return 0;
}
