Loading page…
Practice problem · easy
You work on a chat app. People can accept friend requests, and the app shows each person their friend circle: everyone they are linked to, directly or through other friends. There are n people, numbered 0 to n - 1. At the start nobody is friends with anyone, so there are n circles of one person.
The product team wants a live number on a dashboard: how many circles exist after each accepted request. Your team lead says: "The requests arrive all day, so the number must be ready after every one."
Write groups_after_each_link(n, links).
n is the number of people.links[i] = [a, b] is the i-th accepted request. It makes people a and b friends.i is the number of friend circles after the requests 0 to i have been accepted.A request between two people who are already in one circle does not change the number. If there are no requests, return an empty list.
Input: n = 5, links = [[0, 1], [2, 3], [1, 3], [0, 2], [4, 0]]
Output: [4, 3, 2, 2, 1]Start with 5 circles. A request that joins two different circles lowers the count by 1. A request inside one circle leaves it alone.
| Request | Different circles? | Circles after |
|---|---|---|
| start | 5 | |
| [0, 1] | yes | 4 |
| [2, 3] | yes | 3 |
| [1, 3] | yes: {0, 1} and {2, 3} merge | 2 |
| [0, 2] | no: 0 and 2 are already in one circle | 2 |
| [4, 0] | yes: person 4 joins {0, 1, 2, 3} | 1 |
The answer is [4, 3, 2, 2, 1].
Input: n = 3, links = []
Output: []There are no requests, so there are no entries.
Input: n = 2, links = [[0, 1], [0, 1]]
Output: [1, 1]The first request joins the two people. The second repeats it and changes nothing.
1 ≤ n ≤ 100,0000 ≤ len(links) ≤ 200,000, and every row is [a, b] with 0 ≤ a, b < n and a ≠ bThere can be 100,000 people and 200,000 requests, and you need an answer after each one. Counting the circles from scratch after every request costs about n + m each, so all the requests cost m × (n + m): 60 billion steps. A union-find structure updates the count in nearly constant time per request.
groups_after_each_link · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.