bhupixb

Finding Bridges in a simple undirected graphs

Nov 7th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. class find_bridges{
  5. public:
  6. vector<vector<int>> v;
  7. vector<bool> vis;
  8. vector<int> low, tin;
  9. map<pair<int,int>,int> mp;
  10. int timer, n, m;
  11.  
  12. find_bridges(int x, int y) {
  13. n = x, m = y;
  14. v.resize(n);
  15. timer = 1;
  16. vis.resize(n, 0);
  17. low.resize(n, -1);
  18. tin.resize(n, -1);
  19. }
  20.  
  21. void dfs(int node, int p = -1) {
  22. vis[node] = 1;
  23. tin[node] = low[node] = timer++;
  24. for (int to : v[node]) {
  25. if (to == p) continue;
  26. if (vis[to]) {
  27. low[node] = min(low[node], tin[to]);
  28. }
  29. else {
  30. dfs(to, node);
  31. low[node] = min(low[node], low[to]);
  32.  
  33. // Here the bridge is found
  34. if (low[to] > tin[node]) {
  35. int x = node, y = to;
  36. cout << x+1 << ' ' << y+1 << '\n';
  37. }
  38. }
  39. }
  40. }
  41. void find_bridgesFinal() {
  42. // Assume the graph to be connected
  43. dfs(0);
  44. for (int i = 0; i < n; ++i) {
  45. cout << i+1 << ' ' << low[i] << ' ' << tin[i] << '\n';
  46. }
  47. }
  48. };
  49.  
  50. signed main() {
  51. int t, l, r;
  52. t = 1;
  53. while (t--) {
  54. int n, m;
  55. cin >> n >> m;
  56. find_bridges solver(n, m);
  57. for (int i = 0; i < m; ++i) {
  58. cin >> l >> r;
  59. --l, --r;
  60. solver.v[l].push_back(r);
  61. solver.v[r].push_back(l);
  62. }
  63. solver.find_bridgesFinal();
  64. }
  65. return 0;
  66. }
Add Comment
Please, Sign In to add comment