Number of Connected Components - Advanced Data Structures / Disjoint Set Union | Union Find

Prereq: DSU Introduction

For this question we start with n nodes in a graph that are all independent of each other. We will then begin connecting nodes in the graph. After each connection connecting two different nodes we ask you to compute the number of connected components in a graph. A connected component is a series of node such that there exists a path between any two nodes in the graph. Nodes will be 0-indexed and will be integers from 0 to n - 1.


This is a companion discussion topic for the original entry at https://algo.monster/problems/number_of_connected_components/