Cześć,
Nie zagłębiałem się za mocno w kod. Możliwe, że masz dobry pomysł na rozwiązanie (na pewno jest ciekawy), ale proponuję ci pewną alternatywę. To zadanie można łatwiej zrobić używając zbiorów rozłącznych (finding union). Jest to łatwy algorytm, ale jeśli będziesz mieć problem z jego zrozumieniem napisz do mnie, z chęcią pomogę.
EDIT: Jest prostsze rozwiązanie wykorzystujące tylko algorytm DFS, sorry za mieszanie w głowie.
Mam jeszcze jedną małą podpowiedź. Znacznie za dużo używasz dynamicznego alokowania pamięci. Nie wiem jak jest z OIG'iem, ale na OI'u i innych konkursach programistycznych w celu posiadania tablicy o nieznanej przed wykonaniem programu wielkości używa się klasy vector z STL'a. Polecam ci się z STL'em zapoznać, bo upraszcza wiele spraw i trudniej jest popełnić błąd. Jeżeli odstrasza cię trochę składnia używana przy STL'u, to też z chęcią pomogę, bo jest to naprawdę proste i tylko na pierwszy rzut oka może wydawać się nie do ogarnięcia.
Bardzo ważną rzeczą, której brakuje w twoim kodzie, są dwie funkcje, które zmniejszają czas operacji in/out i są podstawą do zadań algorytmicznych. Zawsze przy używaniu iostream'a jako dwie pierwsze instrukcje funkcji main pisz:
ios_base::sync_with_stdio( 0 );
cin.tie( 0 );
Sprawdzarka wyrzuci przekroczenie limitu czasu, nawet dla poprawnych rozwiązań, bez tych dwóch linijek. Zresztą w ogóle OIG'owe sprawdzarki ponoć są mocno wyśrubowane pod względem czasu i lepiej używać cstdio.