How far would a rumor spread?
Build the final groups first, then answer a size query for each of several starting points. About 10 minutes.
Build first, then answer
This mastery step combines two ideas you already have: keeping each group's size at its leader, and answering several questions against one finished set of groups.
A good habit for problems like this: finish building everything before you answer anything. Then each question is a single lookup: find the person's leader and read the group's size.
- answers
- []
Build first: merge along every connection, keeping each group's size at its leader. Only then answer questions.
Two rumour starters are in the same group of 4 people. What do you return for them?
- A4 and 4
- BTheir own numbers
Show the answer
4 and 4. They share a group, so both rumours reach the same 4 people.
How far would a rumor spread?
There are n people, numbered 0 to n - 1, and edges lists pairs [a, b] meaning a and b know each other, processed in order (knowing is symmetric and travels through a chain of acquaintances, so it works exactly like a union-find merge). For each person in starters, if they started a rumor, return how many people (including themselves) would eventually hear it: the size of their final group. Return the answers in the same order as starters.
n = 5, edges = [[0, 1], [1, 2], [3, 4]], starters = [0, 3] → [3, 2]
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · 1 ≤ starters.length ≤ 100,000 · edges[i] has two different node numbers, each 0 ≤ x < n · every starter is 0 ≤ x < n