Friendship Exit Snapshots
Component sizes of specified nodes after successive graph edge deletions
A social network has members numbered from 0 to n - 1. Each friendship is mutual. A member's circle consists of everyone reachable from that member through zero or more friendships, including the member themself.
friendships[j] = [u, v] describes friendship j. Initially, every listed friendship is active.
The network processes a sequence of exit events. At event i:
- Friendship
removals[i]is permanently deactivated. - The network records the size of member
observers[i]'s circle after that deactivation.
Return these recorded circle sizes in event order. Each friendship appears at most once in removals. Friendships not listed in removals remain active throughout.
Examples
Example 1
Input: n = 4, friendships = [[0,1],[1,2],[2,3]], removals = [1,0], observers = [0,1] Output: [2,1]
Removing friendship 1 splits the original chain into the circles {0, 1} and {2, 3}; observer 0 belongs to the first. Removing friendship 0 next isolates observer 1.
Example 2
Input: n = 4, friendships = [[0,1],[1,2],[2,0],[2,3]], removals = [0,1], observers = [2,3] Output: [4,3]
The first removed friendship lies on a cycle, so observer 2 can still reach every member. After the next removal, member 1 is isolated while observer 3 remains connected to members 0 and 2.
Example 3
Input: n = 1, friendships = [], removals = [], observers = [] Output: []
There are no exit events, so there are no snapshots to record.
Constraints
- 1 <= n <= 100000
- 0 <= friendships.length <= 2000
- Each friendship contains two distinct member IDs in [0, n - 1].
- No unordered pair of members appears more than once in friendships.
- 0 <= removals.length <= friendships.length
- observers.length == removals.length
- Every removals[i] is a valid friendship index, and all removal indices are distinct.
- Every observers[i] is a member ID in [0, n - 1].
The intended solution uses offline reverse processing and union-find with path compression and union by size. Its time complexity is O(n + (m + q) alpha(n)) and its space complexity is O(n + m + q), where m is the number of friendships and q is the number of events.
Hints
Show hint 1Hint 1
Deleting a friendship can split a circle, which is difficult to handle with ordinary union-find. What operation would happen if you processed events backward?
Show hint 2Hint 2
Start with only the friendships that survive all events. In reverse order, record the observer's current component size before restoring that event's friendship.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also report the total number of circles after each event?
- How would you change the query handling if each event asked whether two specified members were in the same circle?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem