Ja widzę przynajmniej trzy możliwości:
1. Utworzyć klasę/strukturę (struktura byłaby bardziej poprawna) przechowującą parę Stringów - nazwa państwa, nazwa stolicy i wrzucić to do jakiegoś kontenera i potem losować index. Albo:
2. Wykorzystać już wbudowane mechanizmy i użyć pair - tak samo, Stringi nazwa państwa i nazwa stolicy. Również wrzucić do jakiegoś kontenera.
3. Użyć mapy gdzie kluczem byłaby nazwa państwa, a wartością nazwa stolicy. Tylko tutaj byłoby o tyle gorzej, że gdzieś musiałbyś przechowywać klucze (i losować index klucza i wyciągać tym kluczem wartość z mapy a potem porównać z inputem użytkownika) albo ustawić iterator na jakimś wylosowanym numerze.
Korzystanie z dwóch kontenerów gdzie w jednym miałbyś nazwy państw a w drugim nazwy stolic, na dłuższą metę jest ciężkie. Sortowanie, usuwanie czy jakiekolwiek inne operacji wymagają działania na dwóch kontenerach.
Teraz tylko pytanie, skąd chcesz pobierać przygotowane dane nazwa państwa - nazwa stolicy? Zakładam, że nie chcesz w trakcie programu prosić, żeby sam podał państwa-stolice. Więc, lepiej będzie jak przygotujesz sobie takie dane i wrzucisz to do jakiejś bazy danych (może być nawet plik .txt). Zdaję sobie sprawę, że państw jest "dużo" więc mógłbyś poszukać jakiegoś zewnętrznego api gdzie miałbyś przygotowane takie dane.