6th March 2022

Computer Science⚑

Theory⚑

Algorithms⚑

• New: Add union-find data structure definition and algorithms.

  In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets.

  It can be used to store the connected components of an undirected graph.

  An example could be:

  0   1---2   3---4
  
  5---6   7   8   9
  

  • N is the number of nodes. Equals to 10 in the example.

  The data structure should support the following operations:

  • initialize(): Set the initial state of the graph.
  • find(p, q): Are nodes p and q connected?
  • union(p,q): Connect nodes p and q.