Loading...
Loading...
Loading...
Students registered for the college tech fest more than once, sometimes with different emails. The fest team wants one record per person.
Each record has a name and some emails. Two records belong to the same person if they share at least one email. This links in chains: if record A shares an email with B, and B shares one with C, then A, B and C are one person. Two different people can have the same name, so a name alone links nothing. Records that share an email always have the same name.
Print one line per person: the name, then all of that person's emails without repeats, in ascending order. Order the lines by their first email, ascending.
. and @.String.compareTo).Example
Input
4 Asha 2 asha@mail.in asha.k@mail.in Ravi 1 ravi@mail.in Asha 2 ak@mail.in asha.k@mail.in Asha 1 asha.r@mail.in
Output
Asha ak@mail.in asha.k@mail.in asha@mail.in Asha asha.r@mail.in Ravi ravi@mail.in
Records 1 and 3 share asha.k@mail.in, so they are one person. The last Asha shares nothing, so she is someone else.
Try the problem first. Open one hint at a time.
Think of each record as a point. Two points are joined when they share an email. A person is a group of joined points.
Groups grow by merging: when a record shares an email with an earlier record, their two whole groups become one.
Remember the first record that used each email in a HashMap. A later record with the same email merges with that record.
Use union-find (disjoint set union) on the records. Then collect each group's emails in a TreeSet and sort the groups by their first email.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor