fork download
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
  3. #define FOD(i, a, b) for (int i = (a); i >= (b); i--)
  4. #define REP(i, n) for (int i = 0; i < (n); i++)
  5. #define ALL(x) (x).begin(), (x).end()
  6. #define __Dennis_Tran___ signed main()
  7. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  8. #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  9.  
  10. using namespace std;
  11.  
  12. const int maxN = 1e5 + 5;
  13.  
  14. int n, m, Num[maxN], Low[maxN], cnt = 0;
  15. vector <int> ke[maxN];
  16. vector <pair <int, int>> ans;
  17.  
  18. void dfs(int u, int par = -1) {
  19. Num[u] = Low[u] = ++cnt;
  20. for (int v : ke[u]) if (v != par) {
  21. if (Num[v]) Low[u] = min(Low[u], Num[v]);
  22. else {
  23. dfs(v, u);
  24. Low[u] = min(Low[u], Low[v]);
  25.  
  26. if (Low[v] == Num[v]) {
  27. ans.emplace_back(min(u, v), max(u, v));
  28. }
  29. }
  30. }
  31. }
  32.  
  33. __Dennis_Tran___{
  34. ios_base::sync_with_stdio(false);
  35. cin.tie(nullptr);
  36. cout.tie(nullptr);
  37.  
  38. cin >> n >> m;
  39. while (m--) {
  40. int u, v; cin >> u >> v;
  41. ke[u].emplace_back(v);
  42. ke[v].emplace_back(u);
  43. }
  44.  
  45. FOR(i, 1, n) if (Num[i] == 0) {
  46. dfs(i);
  47. }
  48.  
  49. sort(ALL(ans));
  50. cout << ans.size() << '\n';
  51. for (auto [u, v] : ans) cout << u << ' ' << v << '\n';
  52. cerr << "Time elapsed: " << TIME << " s.\n";
  53. return (0 ^ 0);
  54. }
Success #stdin #stdout #stderr 0s 2756KB
stdin
5 5
1 2
1 4
2 4
3 5
4 5
stdout
2
3 5
4 5
stderr
Time elapsed: 6.9e-05 s.