Задача: 721. Accounts Merge
Сложность: medium

Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке.

Пример:

nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

👨‍💻 Алгоритм:

1⃣Создайте граф, в котором узлы представляют email-адреса, а ребра соединяют email-адреса, принадлежащие одному аккаунту.

2⃣Пройдите по графу, чтобы найти все связанные компоненты, которые представляют объединенные аккаунты.

3⃣Для каждой связанной компоненты, соберите email-адреса, отсортируйте их и добавьте имя пользователя в начало списка.

😎 Решение:

class Solution {
    func accountsMerge(_ accounts: [[String]]) -> [[String]] {
        var emailToName = [String: String]()
        var graph = [String: Set<String>]()
        
        for account in accounts {
            let name = account[0]
            let firstEmail = account[1]
            for email in account[1...] {
                graph[firstEmail, default: []].insert(email)
                graph[email, default: []].insert(firstEmail)
                emailToName[email] = name
            }
        }
        
        var seen = Set<String>()
        func dfs(_ email: String) -> [String] {
            var stack = [email]
            var result = [String]()
            while !stack.isEmpty {
                let node = stack.removeLast()
                if !seen.contains(node) {
                    seen.insert(node)
                    result.append(node)
                    for neighbor in graph[node, default: []] {
                        stack.append(neighbor)
                    }
                }
            }
            return result
        }
        
        var mergedAccounts = [[String]]()
        for email in emailToName.keys {
            if !seen.contains(email) {
                let emails = dfs(email)
                mergedAccounts.append([emailToName[email]!] + emails.sorted())
            }
        }
        
        return mergedAccounts
    }
}

Ставь 👍 и забирай 📚 Базу знаний