• + 0 comments

    js

    function getGrpCnt(tree, node) {
        let cnt = 0;
        const children = tree[node];
        if (children) {
            delete tree[node];
            cnt++;
            for (const c of children) {
                cnt += getGrpCnt(tree, c);
            }
        }
        return cnt;
    }
    
    function journeyToMoon(n, astronaut) {
        const tree = {};
        for (const [a1, a2] of astronaut) {
            tree[a1] = tree[a1] ?? new Set();
            tree[a2] = tree[a2] ?? new Set();
            tree[a1].add(a2);
            tree[a2].add(a1);
        }
    
        let res = n * (n - 1) / 2;
        for (let a = 0; a < n; a++) {
            const cnt = getGrpCnt(tree, a);
            res -= cnt * (cnt - 1) / 2;
        }
        return res;
    }