fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 100005;
  9. vector<int> adj[MAXN];
  10. bool visited[MAXN];
  11. int tin[MAXN], low[MAXN], timer;
  12. set<pair<int, int>> bridges;
  13.  
  14. bool dfsCheck(int u, int target) {
  15.     visited[u] = true;
  16.     if (u == target) return true;
  17.     for (int v : adj[u]) {
  18.         if (!visited[v] && dfsCheck(v, target)) return true;
  19.     }
  20.     return false;
  21. }
  22.  
  23. vector<pair<int, int>> tim_canh_cau(int n) {
  24.     vector<pair<int, int>> bridgeEdges;
  25.     set<pair<int, int>> checkedEdges;
  26.     for (int u = 1; u <= n; ++u) {
  27.         for (int v : adj[u]) {
  28.             if (u < v && checkedEdges.find({u, v}) == checkedEdges.end()) {
  29.                 checkedEdges.insert({u, v});
  30.                 adj[u].erase(remove(adj[u].begin(), adj[u].end(), v), adj[u].end());
  31.                 adj[v].erase(remove(adj[v].begin(), adj[v].end(), u), adj[v].end());
  32.  
  33.                 fill(visited, visited + n + 1, false);
  34.                 if (!dfsCheck(u, v)) {
  35.                     bridgeEdges.emplace_back(u, v);
  36.                 }
  37.  
  38.                 adj[u].push_back(v);
  39.                 adj[v].push_back(u);
  40.             }
  41.         }
  42.     }
  43.     return bridgeEdges;
  44. }
  45.  
  46. int main() {
  47.     int n, m;
  48.     cin >> n >> m;
  49.     for (int i = 0; i < m; i++) {
  50.         int u, v;
  51.         cin >> u >> v;
  52.         adj[u].push_back(v);
  53.         adj[v].push_back(u);
  54.     }
  55.  
  56.     vector<pair<int, int>> bridges = tim_canh_cau(n);
  57.     cout << bridges.size() << endl;
  58.     for (auto [u, v] : bridges) {
  59.         cout << u << " " << v << endl;
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 6092KB
comments ()
stdin 
5 5
1 2
2 3
3 4
3 5
4 5
stdout 
2
1 2
2 3
https://ideone.com/PU8Js6
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!