dynamic_connectivity.cpp

#include "dynamic_connectivity.hpp"
#include <iomanip>
#include <iostream>

DynamicConnectivity::DynamicConnectivity() {
}

DynamicConnectivity::DynamicConnectivity(long num_nodes) {
  union_find = new std::atomic<Node>[num_nodes];
  for (int i = 0; i < num_nodes; ++i) {
    union_find[i] = i;
  }
}

void DynamicConnectivity::printUF() {
  for (int i = 0; i < 9; ++i) {
    std::cout << i << ": " << union_find[i] << std::endl;
  }
  std::cout << std::endl;
}

void DynamicConnectivity::addEdges(const EdgeList &edges) {
  for (auto [from, to, length] : edges) {
    std::cout << std::setw(2) << from << " | " << std::setw(2) << to
              << std::endl;
    union_find[find_representative(from)] = find_representative(to);
    printUF();
  }
}

bool DynamicConnectivity::connected(Node a, Node b) const {
  return find_representative(a) == find_representative(b);
}

DynamicConnectivity::Node DynamicConnectivity::parentOf(Node n) const {
  return union_find[n];
}

DynamicConnectivity::Node
DynamicConnectivity::find_representative(Node a) const {
  Node current = a;
  Node parent = union_find[current];

  while (current != parent) {
    current = parent;
    parent = union_find[current];
  }

  return parent;
}