We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
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.