Given an undirected graph, find its critical edges. A critical edge is one that when removed disconnects any two connected nodes.
The brute-force solution –removing an edge and checking for connectivity– will work. But this is an implementation using Tarjan’s DFS Bridge finding algorithm.
set<int> apNodes, apVis; set<pair<int, int> > apEdges; void articulationPointAndBridge(map<int, map<int, int> > &graph, int s) { map<int, int> parent, num_dfs, num_low; int children_s = 0, num_dfs_size = 0; stack<int> stk; parent[s] = s, stk.push(s); // dfs while (stk.size()) { int u = stk.top(); // grey if (apVis.find(u) == apVis.end()) { num_dfs[u] = num_low[u] = num_dfs_size++; apVis.insert(u); children_s += u != s && parent[u] == s; for (map<int, int>::reverse_iterator v = graph[u].rbegin(); v != graph[u].rend(); ++v) // grey to white if (apVis.find(v->first) == apVis.end()) parent[v->first] = u, stk.push(v->first); // grey to grey else if (parent[u] != v->first) num_low[u] = min(num_low[u], num_dfs[v->first]); } // black else { if (parent[u] != u) { // POINTS if (num_dfs[parent[u]] <= num_low[u]) apNodes.insert(parent[u]); // BRIDGES if (num_dfs[parent[u]] < num_low[u]) if (u < parent[u]) apEdges.insert(make_pair(u, parent[u])); else apEdges.insert(make_pair(parent[u], u)); num_low[parent[u]] = min(num_low[parent[u]], num_low[u]); } stk.pop(); } } apNodes.erase(s); if (children_s > 1) apNodes.insert(s); } int main() { string str; int n, a, b, m; while (cin >> n) { // input map<int, map<int, int> > graph; for (int i = 0; i < n; ++i) { cin >> a; cin >> str; stringstream ss(str.substr(1, str.length() - 2)); ss >> m; for (int j = 0; j < m; ++j) cin >> b, graph[a][b] = graph[b][a] = 1; } // solve apVis.clear(), apEdges.clear(), apNodes.clear(); for (map<int, map<int, int> >::iterator i = graph.begin(); i != graph.end(); ++i) if (apVis.find(i->first) == apVis.end()) articulationPointAndBridge(graph, i->first); // print cout << apEdges.size() << " critical links"; for (set<pair<int, int> >::iterator i = apEdges.begin(); i != apEdges.end(); ++i) cout << endl << i->first << " - " << i->second; cout << endl << endl; } }