#ЛитКод
Задача: 721. Accounts Merge

Дан список аккаунтов, в котором каждый элемент 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-адреса, отсортируйте их и добавьте имя пользователя в начало списка.

😎 Решение:

function accountsMerge($accounts) {
    $emailToName = [];
    $graph = [];
    
    foreach ($accounts as $account) {
        $name = $account[0];
        $firstEmail = $account[1];
        foreach (array_slice($account, 1) as $email) {
            if (!isset($graph[$firstEmail])) $graph[$firstEmail] = [];
            if (!isset($graph[$email])) $graph[$email] = [];
            $graph[$firstEmail][] = $email;
            $graph[$email][] = $firstEmail;
            $emailToName[$email] = $name;
        }
    }
    
    $seen = [];
    $mergedAccounts = [];
    
    foreach ($emailToName as $email => $name) {
        if (!isset($seen[$email])) {
            $emails = [];
            $stack = [$email];
            while (!empty($stack)) {
                $node = array_pop($stack);
                if (!isset($seen[$node])) {
                    $seen[$node] = true;
                    $emails[] = $node;
                    foreach ($graph[$node] as $neighbor) {
                        $stack[] = $neighbor;
                    }
                }
            }
            sort($emails);
            $mergedAccounts[] = array_merge([$name], $emails);
        }
    }
    
    return $mergedAccounts;
}

👉Новости 👉База вопросов