Challenge can be found here
People connect with each other in a social network. A connection
between Person I and Person J is represented as M I J. When two persons
belonging to different communities connect, the net effect is the
merger of both communities which I and J belongs to.
At the beginning, there are N people representing N communities. Suppose
person 1 and 2 connected and later 2 and 3 connected, then 1,2, and 3 will
belong to the same community.
There are two type of queries:
M I J => communities containing person I and J merged (if they belong to
different communities).
Q I => print the size of the community to which person belongs.
Input Format
The first line of input will contain integers N and Q, i.e. the number
of people and the number of queries. The next Q lines will contain the
queries.
Constraints :
1 <= N <= 100000
1 <= Q <= 200000
My code times out for 6 / 9 test-cases, so obviously this can be improved a lot.
Any suggestions would be much appreciated.