Merge Accounts by Shared Identifiers

Implement merge_accounts(accounts: list[list[str]]) -> list[list[str]].

Each account is [name, email1, email2, ...]. Two accounts belong to the same person if they share an email directly or through a chain of shared emails. All accounts in one connected group are guaranteed to have the same name.

Return one row per group: the name followed by all distinct emails in lexicographic order. Sort result rows by name and then by the first email. Every account contains at least one email, so the second sort key always exists.

Valid Input Domain

• Names and emails are nonempty case-sensitive strings.
• Duplicate emails within one account have no additional effect.

Constraints

• 0 <= accounts.length <= 100,000
• The total number of email occurrences is at most 300,000.

Public Examples

Example 1

Input: [["Lee", "a@x.test", "b@x.test"], ["Lee", "b@x.test", "c@x.test"], ["Mina", "m@x.test"]]

Output: [["Lee", "a@x.test", "b@x.test", "c@x.test"], ["Mina", "m@x.test"]]

Example 2

Input: [["Ari", "z@x.test"], ["Ari", "a@x.test"], ["Ari", "z@x.test", "y@x.test"]]

Output: [["Ari", "a@x.test"], ["Ari", "y@x.test", "z@x.test"]]

Hint: Model identifier connectivity

The grouping relation is transitive even when two accounts do not share an email directly.