721. 账户合并

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        graph = collections.defaultdict(list)
        name_of = {}
        for acc in accounts:
            first = acc[1]
            for email in acc[1:]:
                name_of[email] = acc[0]
                graph[first].append(email)
                graph[email].append(first)
        seen = set()
        res = []
        for email in name_of:
            if email in seen:
                continue
            seen.add(email)
            stack, comp = [email], []
            while stack:
                u = stack.pop()
                comp.append(u)
                for v in graph[u]:
                    if v not in seen:
                        seen.add(v)
                        stack.append(v)
            res.append([name_of[email]] + sorted(comp))
        return res

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, String> nameOf = new HashMap<>();
        for (List<String> acc : accounts) {
            String first = acc.get(1);
            for (int k = 1; k < acc.size(); k++) {
                String email = acc.get(k);
                nameOf.put(email, acc.get(0));
                graph.computeIfAbsent(first, x -> new ArrayList<>()).add(email);
                graph.computeIfAbsent(email, x -> new ArrayList<>()).add(first);
            }
        }
        Set<String> seen = new HashSet<>();
        List<List<String>> res = new ArrayList<>();
        for (String email : nameOf.keySet()) {
            if (seen.contains(email)) continue;
            seen.add(email);
            Deque<String> stack = new ArrayDeque<>();
            stack.push(email);
            List<String> comp = new ArrayList<>();
            while (!stack.isEmpty()) {
                String u = stack.pop();
                comp.add(u);
                for (String v : graph.get(u)) {
                    if (seen.add(v)) stack.push(v);
                }
            }
            Collections.sort(comp);
            List<String> row = new ArrayList<>();
            row.add(nameOf.get(email));
            row.addAll(comp);
            res.add(row);
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, vector<string>> graph;
        unordered_map<string, string> nameOf;
        for (auto& acc : accounts) {
            const string& first = acc[1];
            for (int k = 1; k < (int)acc.size(); k++) {
                nameOf[acc[k]] = acc[0];
                graph[first].push_back(acc[k]);
                graph[acc[k]].push_back(first);
            }
        }
        unordered_set<string> seen;
        vector<vector<string>> res;
        for (auto& [email, name] : nameOf) {
            if (seen.count(email)) continue;
            seen.insert(email);
            vector<string> stack = {email}, comp;
            while (!stack.empty()) {
                string u = stack.back();
                stack.pop_back();
                comp.push_back(u);
                for (auto& v : graph[u]) {
                    if (!seen.count(v)) {
                        seen.insert(v);
                        stack.push_back(v);
                    }
                }
            }
            sort(comp.begin(), comp.end());
            vector<string> row = {name};
            row.insert(row.end(), comp.begin(), comp.end());
            res.push_back(row);
        }
        return res;
    }
};

func accountsMerge(accounts [][]string) [][]string {
	graph := map[string][]string{}
	nameOf := map[string]string{}
	for _, acc := range accounts {
		first := acc[1]
		for _, email := range acc[1:] {
			nameOf[email] = acc[0]
			graph[first] = append(graph[first], email)
			graph[email] = append(graph[email], first)
		}
	}
	seen := map[string]bool{}
	res := [][]string{}
	for email, name := range nameOf {
		if seen[email] {
			continue
		}
		seen[email] = true
		stack, comp := []string{email}, []string{}
		for len(stack) > 0 {
			u := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			comp = append(comp, u)
			for _, v := range graph[u] {
				if !seen[v] {
					seen[v] = true
					stack = append(stack, v)
				}
			}
		}
		sort.Strings(comp)
		res = append(res, append([]string{name}, comp...))
	}
	return res
}

var accountsMerge = function(accounts) {
    const graph = new Map(), nameOf = new Map();
    const link = (a, b) => {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a).push(b);
    };
    for (const acc of accounts) {
        const first = acc[1];
        for (const email of acc.slice(1)) {
            nameOf.set(email, acc[0]);
            link(first, email);
            link(email, first);
        }
    }
    const seen = new Set(), res = [];
    for (const [email, name] of nameOf) {
        if (seen.has(email)) continue;
        seen.add(email);
        const stack = [email], comp = [];
        while (stack.length) {
            const u = stack.pop();
            comp.push(u);
            for (const v of graph.get(u)) {
                if (!seen.has(v)) {
                    seen.add(v);
                    stack.push(v);
                }
            }
        }
        comp.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
        res.push([name, ...comp]);
    }
    return res;
};

function accountsMerge(accounts: string[][]): string[][] {
    const graph = new Map<string, string[]>(), nameOf = new Map<string, string>();
    const link = (a: string, b: string): void => {
        if (!graph.has(a)) graph.set(a, []);
        graph.get(a)!.push(b);
    };
    for (const acc of accounts) {
        const first = acc[1];
        for (const email of acc.slice(1)) {
            nameOf.set(email, acc[0]);
            link(first, email);
            link(email, first);
        }
    }
    const seen = new Set<string>(), res: string[][] = [];
    for (const [email, name] of nameOf) {
        if (seen.has(email)) continue;
        seen.add(email);
        const stack = [email], comp: string[] = [];
        while (stack.length) {
            const u = stack.pop()!;
            comp.push(u);
            for (const v of graph.get(u)!) {
                if (!seen.has(v)) {
                    seen.add(v);
                    stack.push(v);
                }
            }
        }
        comp.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
        res.push([name, ...comp]);
    }
    return res;
}