Test case 11 doesn't work with the function signature in rust. The answer is > i32::MAX.

For python code, test case 11, if you use summation over and over for calculating the final results, you could use cummulative sum to avoid it. it will help you to speed up.

Runtime error on #11 testcase others are successfully executed

int parent[100001]; int Size[100001];

void make(int n){ for(int i=0;i

int find(int vertex){ if(parent[vertex]==vertex)return vertex; return parent[vertex]=find(parent[vertex]); }

void Union(int a,int b){ a=find(a); b=find(b); if(a==b)return ; if(Size[b]>Size[a])swap(a,b); parent[b]=a; Size[a]+=Size[b]; }

int journeyToMoon(int n, vector> astronaut) { make(n);

for(int i=0;i<astronaut.size();i++){
    if(find(astronaut[i][0])!=find(astronaut[i][1])){
        Union(astronaut[i][0],astronaut[i][1]);
    }
}
long long ans=0;
vector<int> a;
for(int i=0;i<n;i++){
    if(parent[i]==i){
        a.push_back(Size[i]);
    }
}
for(int i=0;i<a.size();i++){
    for(int j=i+1;j<a.size();j++)ans+=(a[i]*a[j]);
}
return ans;

I don't know how anyone solved this in Python without special handling for Test Case #11, in which there are 100000 single-astronaut countries. Look at the test case data! Once I computed the "disjoint sets" using normal graph algorithms (this is actually just an array of subgraph sizes, since it doesn't matter which nodes go into a subgraph), I could calculate possible astronaut pairs from single-astronaut countries as number of singletons * (number of singletons - 1) // 2, and so on.

Python solution based on : * Adjancency List * Breadth First Search * Combination for pairing with each other ungrouped

def journeyToMoon(n, astronaut):

matrix = [ [] for _ in range(n) ] 

Vertex = set()

for a in astronaut:
    _a , _b = a
    matrix[ _a ].append(_b)
    matrix[ _b ].append(_a)

    Vertex.add(_a)
    Vertex.add(_b)


rank = 0

visited = [ False ] * n

print(Vertex)

_G = []

for i in Vertex:

    if not visited[i]:
        G = []
        q = [ i ]
        while q:

            curr = q[0]
            q = q[1:]

            G.append(curr)

            visited[curr] = True

            for x in matrix[curr]:
                if not visited[x]:
                    visited[x] = True
                    q.append(x)

        _G.append(G)

# unorganize
n -= sum([ len(g) for g in _G ])

print(f"re {n}")


# print(" --> ",_G)

result = 0

for i in range(len(_G)):
    _ii = len(_G[i])

    for j in range(i + 1 ,len(_G)):
        result += _ii * len(_G[j])

    result += _ii * n

return result + (( n * (n-1) ) // 2)