Accounts Merge solution and explanation

from collections import defaultdict

def accountsMerge(accounts):
    email_graph = defaultdict(set)
    email_to_name = {}

    for account in accounts:
        name = account[0]
        emails = account[1:]
        first_email = emails[0]

        for email in emails:
            email_graph[first_email].add(email)
            email_graph[email].add(first_email)
            email_to_name[email] = name

    visited = set()
    def dfs(email):
        visited.add(email)
        component = [email]
        for neighbor in email_graph[email]:
            if neighbor not in visited:
                component.extend(dfs(neighbor))
        return component

    output = []
    for email in email_graph:
        if email not in visited:
            connected_emails = dfs(email)
            output.append([email_to_name[email]] + sorted(connected_emails))

    return output

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <string>
using namespace std;

void dfs(const string &email, unordered_map<string, unordered_set<string>> &emailGraph,
         unordered_set<string> &visited, vector<string> &component) {
    visited.insert(email);
    component.push_back(email);
    for (const string &neighbor : emailGraph[email]) {
        if (!visited.count(neighbor)) {
            dfs(neighbor, emailGraph, visited, component);
        }
    }
}

vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
    unordered_map<string, unordered_set<string>> emailGraph;
    unordered_map<string, string> emailToName;

    // Build the graph
    for (const auto &account : accounts) {
        const string &name = account[0];
        for (int j = 1; j < account.size(); ++j) {
            emailGraph[account[1]].insert(account[j]);
            emailGraph[account[j]].insert(account[1]);
            emailToName[account[j]] = name;
        }
    }

    // DFS to find connected components
    unordered_set<string> visited;
    vector<vector<string>> result;
    for (const auto &pair : emailGraph) {
        const string &email = pair.first;
        if (!visited.count(email)) {
            vector<string> component;
            dfs(email, emailGraph, visited, component);
            sort(component.begin(), component.end());
            component.insert(component.begin(), emailToName[email]);
            result.push_back(component);
        }
    }
    return result;
}

import java.util.*;

public class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                emailToName.put(account.get(i), name);
                parent.put(account.get(i), account.get(i));
            }
        }

        for (List<String> account : accounts) {
            String p = find(account.get(1), parent);
            for (int i = 2; i < account.size(); i++) {
                parent.put(find(account.get(i), parent), p);
            }
        }

        Map<String, TreeSet<String>> unions = new HashMap<>();
        for (List<String> account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                String root = find(account.get(i), parent);
                unions.computeIfAbsent(root, x -> new TreeSet<>()).add(account.get(i));
            }
        }

        List<List<String>> result = new ArrayList<>();
        for (String root : unions.keySet()) {
            List<String> emails = new ArrayList<>(unions.get(root));
            emails.add(0, emailToName.get(root));
            result.add(emails);
        }
        return result;
    }

    private String find(String s, Map<String, String> parent) {
        return parent.get(s) == s ? s : find(parent.get(s), parent);
    }
}

var accountsMerge = function(accounts) {
    const emailToName = {};
    const parent = {};
    const find = (x) => parent[x] !== x ? parent[x] = find(parent[x]) : x;

    for (const acc of accounts) {
        for (let i = 1; i < acc.length; i++) {
            parent[acc[i]] = acc[i];
            emailToName[acc[i]] = acc[0];
        }
    }

    for (const acc of accounts) {
        const p = find(acc[1]);
        for (let i = 2; i < acc.length; i++) {
            parent[find(acc[i])] = p;
        }
    }

    const unions = {};
    for (const acc of accounts) {
        for (let i = 1; i < acc.length; i++) {
            const root = find(acc[i]);
            if (!unions[root]) unions[root] = new Set();
            unions[root].add(acc[i]);
        }
    }

    const result = [];
    for (const root in unions) {
        const emails = Array.from(unions[root]).sort();
        emails.unshift(emailToName[root]);
        result.push(emails);
    }

    return result;
};

class UnionFind {
    private p: number[];
    private size: number[];

    constructor(n: number) {
        this.p = new Array(n);
        this.size = new Array(n);
        for (let i = 0; i < n; ++i) {
            this.p[i] = i;
            this.size[i] = 1;
        }
    }

    find(x: number): number {
        if (this.p[x] !== x) {
            this.p[x] = this.find(this.p[x]);
        }
        return this.p[x];
    }

    union(a: number, b: number): boolean {
        let pa = this.find(a),
            pb = this.find(b);
        if (pa === pb) {
            return false;
        }
        if (this.size[pa] > this.size[pb]) {
            this.p[pb] = pa;
            this.size[pa] += this.size[pb];
        } else {
            this.p[pa] = pb;
            this.size[pb] += this.size[pa];
        }
        return true;
    }
}

function accountsMerge(accounts: string[][]): string[][] {
    const n = accounts.length;
    const uf = new UnionFind(n);
    const d = new Map<string, number>();

    for (let i = 0; i < n; ++i) {
        for (let j = 1; j < accounts[i].length; ++j) {
            const email = accounts[i][j];
            if (d.has(email)) {
                uf.union(i, d.get(email)!);
            } else {
                d.set(email, i);
            }
        }
    }

    const g = new Map<number, Set<string>>();
    for (let i = 0; i < n; ++i) {
        const root = uf.find(i);
        if (!g.has(root)) {
            g.set(root, new Set<string>());
        }
        const emailSet = g.get(root)!;
        for (let j = 1; j < accounts[i].length; ++j) {
            emailSet.add(accounts[i][j]);
        }
    }

    const ans: string[][] = [];
    for (const [root, emails] of g.entries()) {
        const emailList = Array.from(emails).sort();
        const mergedAccount = [accounts[root][0], ...emailList];
        ans.push(mergedAccount);
    }

    return ans;
}

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
	pa, pb := uf.find(a), uf.find(b)
	if pa == pb {
		return false
	}
	if uf.size[pa] > uf.size[pb] {
		uf.p[pb] = pa
		uf.size[pa] += uf.size[pb]
	} else {
		uf.p[pa] = pb
		uf.size[pb] += uf.size[pa]
	}
	return true
}

func accountsMerge(accounts [][]string) (ans [][]string) {
	n := len(accounts)
	uf := newUnionFind(n)
	d := make(map[string]int)
	for i := 0; i < n; i++ {
		for _, email := range accounts[i][1:] {
			if j, ok := d[email]; ok {
				uf.union(i, j)
			} else {
				d[email] = i
			}
		}
	}
	g := make(map[int]map[string]struct{})
	for i := 0; i < n; i++ {
		root := uf.find(i)
		if _, ok := g[root]; !ok {
			g[root] = make(map[string]struct{})
		}
		for _, email := range accounts[i][1:] {
			g[root][email] = struct{}{}
		}
	}
	for root, s := range g {
		emails := []string{}
		for email := range s {
			emails = append(emails, email)
		}
		sort.Strings(emails)
		account := append([]string{accounts[root][0]}, emails...)
		ans = append(ans, account)
	}
	return
}