dynamic_connectivity.hpp

#pragma once

#include "edge_list.hpp"
#include <atomic>

class DynamicConnectivity {
public:
  using Node = long;

  DynamicConnectivity();
  explicit DynamicConnectivity(long num_nodes);

  // should contain #pragma omp parallel for
  void addEdges(const EdgeList &edges);

  bool connected(Node a, Node b) const;

  // Must return -1 for roots.
  Node parentOf(Node n) const;
  void printUF();

private:
  std::atomic<Node> *union_find;
  std::atomic<uint> *component_size;

  Node find_representative(Node a) const;
};