LC: 1101. The Earliest Moment When Everyone Become Friends - spiralgo/algorithms GitHub Wiki

1101. The Earliest Moment When Everyone Become Friends:

The Essence:

Noticing that the acquaintance relationship is symmetric as well as transitive is the key. In other words, if A is acquainted with B and B is acquainted with C, then A is acquainted with C too. This way, groups of acquaintance can be thought of as connected nodes of a graph.

Details:

The groups of acquaintance structure can be represented for this purpose using the Disjoint-set data structure. For each group of acquaintance, some node can be designated to be the root of this connected component. When the number of children of this root becomes the given number N, this means that the group of acquaintance contains every single person. The timestamp of this event is to be returned.