I did an n^2 solution and it TLEd on 2 cases. The only thing that comes to mind is union find, but I haven't tried implementing yet. Any ideas?