All problems

Pen Pal Circles

Medium · union find

A school runs a pen-pal scheme. Every letter that has been posted is recorded as a pair [sender, receiver] of first names.

Two children are in the same circle if letters link them, directly or through other children, in either direction. If Ana wrote to Bo and Eli wrote to Bo, then Ana, Bo and Eli are all in one circle, even though Ana and Eli never wrote to each other.

Only children who appear in at least one letter count. A child who writes to themselves forms a circle of one. Names are case-sensitive, so "ana" and "Ana" are different children.

Return the number of circles. If there are no letters, return 0.

Examples

Example 1

Input: letters = [["Ana", "Bo"], ["Cy", "Di"], ["Eli", "Bo"]]

Output: 2

Ana, Bo and Eli are linked through Bo. Cy and Di form the other circle.

Example 2

Input: letters = [["Max", "Max"]]

Output: 1

Writing to yourself still makes one circle of one child.

Example 3

Input: letters = [["a", "b"], ["c", "d"], ["b", "c"]]

Output: 1

The last letter joins the two pairs into a single circle.

Constraints

• 0 <= len(letters) <= 10^5
• Each letter has exactly two names: the sender and the receiver.
• Each name is 1 to 12 letters or digits long.
• The sender and the receiver may be the same child.