Program for finding connected components using quick-find

connected-components.cpp

#ifndef __GRAPH_H_INCLUDED__
#define __GRAPH_H_INCLUDED__

#include <vector>
#include <iostream>
#include <cassert>

class ConnectedComponents {
private:
  std::vector<int> set;
  int num_components;

public:
  void init(int num_vertices) {
    for (int i = 0; i < num_vertices; ++i) {
      set.push_back(i);
    }
    num_components = num_vertices;
  }
  int find(int vertex) {
    assert(vertex < set.size());
    return set[vertex];
  }
  bool connected(int p, int q) { return find(p) == find(q); }
  void make_union(int p, int q) {
    int setp = find(p);
    int setq = find(q);
    if (setp == setq) { return; }
    for (int i = 0; i < set.size(); ++i) {
      if (set[i] == setp) { set[i] = setq; }
    }
    --num_components;
  }
  void print() {
    std::cout << "COMPONENTS:" << num_components << ". GRAPH: ";
    for (int i = 0; i < set.size(); ++i) {
      std::cout << set[i];
    }
    std::cout << std::endl;
  }
};

#endif // __GRAPH_H_INCLUDED__


#include "graph.h"

int main() {
  ConnectedComponents g;
  std::cout << "VERTICES: ";
  int num_vertices;
  std::cin >> num_vertices;
  g.init(num_vertices);
  int i, j;
  while (std::cin >> i >> j) {
    g.make_union(i, j);
    g.print();
  }
}