Journey to the Moon

• Time : O(alogn)
• Space : O(n)

c++

int uf[100001];
int find(int u) {
    return u == uf[u] ? u : uf[u] = find(uf[u]);
}
void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu, pv);
}
long long journeyToMoon(long long n, vector<vector<int>> astronaut) {
    for(int i = 0; i < n; i++) uf[i] = i;
    for(auto& a : astronaut) {
        int u = a[0], v = a[1];
        uni(u, v);
    }
    unordered_map<int, long long> freq;
    for(int i = 0; i < n; i++) freq[find(i)]++;
    long long res = 0;
    for(auto& [_, f] : freq) {
        res += f * (n - f);
    }
    return res / 2;
}