Thought Process

This was a fun and simple problem!

Image every caller ID is a node, and we create an edge between 2 nodes if a call is made between them, then the problem can easily be stated as finding when the connected component of the prime minister has more than 990,000 members.

We could just run a BFS each time we add an edge, but since the graph is large this would take a lot of time. Instead, we dynamically update every connected component as we add the calls, this way we don't need to run BFS at all!

The idea is simple:

1. Let every connected component have a representative element this way we can keep track of which connected component every node lives in

   1. Initialize array V such that V[i] is equal to the representative of the connected component i is inside

      • Initially every vertex is its own connected component hence, V[i] = i

   2. Initialize dictionary cc such that cc[i] = all the elements inside the connected component with representative i

      • Same as above, we start with cc[i] = {i}

2. Lets say caller, i, calls, j. Suppose i < j.

   1. Find which connected component they are in from V (Using V[i], V[j])

   2. We will merge cc[V[j] into cc[V[i]]

      • Change the representative of every element in cc[V[j]] to V[i]

   3. Then we can delete cc[V[j]]