I used a little different approach from the one mentioned on this board. It was based on weighted quick-union described by Sedgewick... I made a stupid logical mistake which caused my program to work the longest time possible, so first I got TLE#10 (solutionID=861144). Then I optimized my code with path compression (see Sedgewick once again) and got AC in 0.125 sec (solutionID=861147). Then I realized my error, removed path compression and got AC in 0.078 s (solutionID=861151). Adding path compression back slowed my solution a bit (0.109 s, solutionID=861153). All my solutions consume 449 KB of memory.

I'm interested in time and memory requirements of other possible algorithms. I haven't got their implementations, so I cann't submit them myself.

If somebody feels interested about my approach to this problem, just let me know - I'll explain.