Union-Find

Posted on 2019-05-13 Edited on 2020-12-10 Valine:

This article introduces the Union-Find algorithm.

Introduction

Union-Find algorithm is used to check whether an undirected graph (without any self-loop) contains a cycle.

Keep track of the subsets in a 1D array, named parent[].

For each edge, make su