Next

Count the people behind merged user accounts

Write codeEasy15 minMeta style

Your task

A sign-up system creates duplicate accounts when one person registers twice. Support staff record merges: each one says that two accounts belong to the same person.

Write count_people(n, merges) that returns how many different people the accounts belong to.

Input and output:

  • n: the number of accounts, from 1 to 100,000. Accounts are numbered 0 to n - 1.
  • merges: a list of up to 100,000 pairs [a, b], where a and b are account numbers.
  • Returns an integer.

Rules:

  • Each account starts as its own person.
  • Two accounts belong to the same person if a chain of merges connects them, in any order and in either direction.
  • A merge can repeat an earlier one or name the same account twice. Neither changes the count.

Examples

count_people(n: int, merges: list[list[int]]) -> int
Example 1
Inputcount_people(5, [[0, 1], [1, 2], [3, 4]])
Output2
Example 2
Inputcount_people(6, [[0, 5], [5, 0], [2, 2]])
Output5