Loading...
Loading...
Loading...
Priya is building a backup feature for her college's chat app. In the app, each person is a Person object with an id and a list of Person objects who are their friends. Friendship works both ways.
The backup starts from person s. It must copy s and everyone linked to s through friends, friends of friends, and so on. Every copied person must be a new object, and the copies must be friends with each other exactly as the originals are. People who cannot be reached from s are not copied.
Print the copied network by walking through the new objects only.
Example 1
Input
5 4 1 2 2 3 3 1 4 5 2
Output
3 1: 2 3 2: 1 3 3: 1 2
Persons 1, 2 and 3 are all friends with each other. Persons 4 and 5 cannot be reached from 2, so they are not copied.
Example 2
Input
3 1 1 2 3
Output
1 3:
Person 3 has no friends, so the copy holds only person 3.
Try the problem first. Open one hint at a time.
Keep a HashMap from each original person to their copy. It tells you whether a person has been copied already.
Walk the original network from s with a queue. When you meet a person who has no copy yet, create the copy, store it in the map and add the original to the queue.
For every original person taken out of the queue, add the copy of each friend to their own copy's friend list. Look the friend's copy up in the map instead of creating a new one.
To print, walk the copied objects from the copy of s, collect them, and sort by id.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor