My Learning Blog

Disjoint Set Union - 721 - 6/6/2024

Disjoint Set Union is also called Union Find because of its two operations - union and find.

DSU stands for “Disjoint Set Union,” which is also known as the Union-Find algorithm. It’s a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. It’s particularly useful for dealing with dynamic connectivity queries, such as determining whether two elements are in the same subset or merging two subsets into one.

The two main operations of the Disjoint Set Union data structure are:

721: Accounts Merge

Input: accounts = [[“John”,””,””],[“John”,””,””],[“Mary”,””],[“John”,”“]]

Output: [[“John”,””,””,””],[“Mary”,””],[“John”,”“]]

class UnionFind {
    id: Map<string, string>;

    constructor() { = new Map();

    find(x: string): string {
        if (! return x;

        let y =!;
        if (y !== x) {
            y = this.find(y);
  , y);
        return y;

    union(x: string, y: string): void {, this.find(y));

function accountsMerge(accounts: string[][]): string[][] {
    const dsu = new UnionFind()
    const userEmails = new Set<string>()

    for (const account of accounts) {
        const [name, ...emails] = account
        let emailP = null
        for (const email of emails) {
            let userEmail = `${name},${email}`
            if (emailP === null) {
                emailP = userEmail
            } else {
                dsu.union(emailP, userEmail)

    const group = new Map()
    for(const userEmail of userEmails){
        const ancestor = dsu.find(userEmail)

    const res = []
    for(const [userEmail,childs] of group){
        const [name,_] = userEmail.split(',')
        const oneEntry = [name]
        for(let child of childs.sort()){
            const [_,email] = child.split(',')

    return res