Advertisement
Guest User

Untitled

a guest
Jul 26th, 2016
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.94 KB | None | 0 0
  1. #include <algorithm>
  2. #include <utility>
  3. #include <vector>
  4.  
  5. using Graph = std::vector<std::vector<int>>;
  6. using Edge = std::pair<int, int>;
  7.  
  8. class BridgeHelper {
  9. const Graph& graph;
  10. std::vector<int> ord, low;
  11. int k = 0;
  12.  
  13. public:
  14. std::vector<Edge> bridges;
  15.  
  16. BridgeHelper(const Graph& graph) : graph(graph), ord(graph.size(), -1), low(graph.size()) {
  17. for (int u = 0; u < graph.size(); ++u) {
  18. if (ord[u] >= 0) continue;
  19. dfs(u);
  20. }
  21. }
  22. bool is_bridge(int u, int v) const {
  23. if (ord[u] > ord[v]) std::swap(u, v);
  24. return ord[u] < low[v];
  25. }
  26.  
  27. private:
  28. void dfs(int u, int p = -1) {
  29. ord[u] = low[u] = k;
  30. ++k;
  31. for (int v : graph[u]) {
  32. if (v == p) continue;
  33. if (ord[v] >= 0) {
  34. low[u] = std::min(low[u], ord[v]);
  35. } else {
  36. dfs(v, u);
  37. low[u] = std::min(low[u], low[v]);
  38. }
  39. if (is_bridge(u, v)) bridges.emplace_back(u, v);
  40. }
  41. }
  42. };
  43.  
  44. struct BICC {
  45. std::vector<std::vector<int>> comps;
  46. std::vector<int> belongs;
  47. const BridgeHelper bridge_helper;
  48.  
  49. private:
  50. const Graph& graph;
  51.  
  52. public:
  53. BICC(const Graph& graph) : graph(graph), bridge_helper(graph), belongs(graph.size(), -1) {
  54. for (const auto& bridge : bridge_helper.bridges) {
  55. add_component(bridge.first);
  56. add_component(bridge.second);
  57. }
  58. add_component(0);
  59. }
  60. Graph to_tree() const {
  61. Graph tree(comps.size());
  62. for (const auto& bridge : bridge_helper.bridges) {
  63. int u = belongs[bridge.first], v = belongs[bridge.second];
  64. tree[u].emplace_back(v);
  65. tree[v].emplace_back(u);
  66. }
  67. return tree;
  68. }
  69.  
  70. private:
  71. void fill_component(int c, int u) {
  72. comps[c].emplace_back(u);
  73. belongs[u] = c;
  74. for (int v : graph[u]) {
  75. if (belongs[v] >= 0) continue;
  76. if (bridge_helper.is_bridge(u, v)) continue;
  77. fill_component(c, v);
  78. }
  79. }
  80. void add_component(int u) {
  81. if (belongs[u] >= 0) return;
  82. comps.emplace_back();
  83. fill_component(comps.size() - 1, u);
  84. }
  85. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement