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;
  }

  component_size = new std::atomic<uint>[num_nodes];
  for (int i = 0; i < num_nodes; ++i) {
    component_size[i] = 1;
  }
}

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;

    // find bigger component
    Node root_from = find_representative(from);
    Node root_to = find_representative(to);

    if (component_size[root_from] > component_size[root_to]) {
      union_find[root_to] = root_from;
      component_size[root_from] += component_size[root_to];
    }else{
      union_find[root_from] = root_to;
      component_size[root_to] += component_size[root_from];
    }

    // 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];
  }

  // path compression
  Node representative = parent;
  current = a;
  parent = union_find[current];
  while (current != parent) {
    union_find[current] = representative;
    current = parent;
    parent = union_find[current];
  }


  return parent;
}