Medium · Graphs

Merging Communities

Given n people numbered 1 to n, each starting in their own community, and q operations read as text — "M i j" merges the communities of i and j, "Q i" asks for the size of i's community — print the answer to each Q on its own line.

Examples

Example 1

{
  "n": 6,
  "ops": [
    ["M", 1, 2],
    ["M", 3, 4],
    ["Q", 1],
    ["M", 2, 4],
    ["Q", 3],
    ["M", 5, 6],
    ["Q", 5],
    ["M", 4, 5],
    ["Q", 1]
  ]
}

Output: prints 2, 4, 2, 6

Example 2

{
  "n": 7,
  "ops": [
    ["M", 1, 2],
    ["M", 2, 3],
    ["Q", 3],
    ["M", 5, 6],
    ["M", 6, 7],
    ["Q", 7],
    ["M", 3, 7],
    ["Q", 1],
    ["M", 4, 4],
    ["Q", 4]
  ]
}

Output: prints 3, 3, 6, 1

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.