fork download
copy 
  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.     for (int u = 1; u <= n; ++u) {
  26.         for (int v : adj[u]) {
  27.             if (u < v) {
  28.                 adj[u].erase(remove(adj[u].begin(), adj[u].end(), v), adj[u].end());
  29.                 adj[v].erase(remove(adj[v].begin(), adj[v].end(), u), adj[v].end());
  30.  
  31.                 fill(visited, visited + n + 1, false);
  32.                 if (!dfsCheck(u, v)) {
  33.                     bridgeEdges.emplace_back(u, v);
  34.                 }
  35.  
  36.                 adj[u].push_back(v);
  37.                 adj[v].push_back(u);
  38.             }
  39.         }
  40.     }
  41.     return bridgeEdges;
  42. }
  43.  
  44. int main() {
  45.     int n, m;
  46.     cin >> n >> m;
  47.     for (int i = 0; i < m; i++) {
  48.         int u, v;
  49.         cin >> u >> v;
  50.         adj[u].push_back(v);
  51.         adj[v].push_back(u);
  52.     }
  53.  
  54.     vector<pair<int, int>> bridges = tim_canh_cau(n);
  55.     cout << bridges.size() << endl;
  56.     for (auto [u, v] : bridges) {
  57.         cout << u << " " << v << endl;
  58.     }
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5832KB
comments ()
stdin
copy 
5 5
1 2
2 3
3 4
3 5
4 5
stdout
copy 
3
1 2
2 3
2 3
https://ideone.com/mwwcbL
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!