Connect cities

#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>


using namespace std;

int main()
{
    int n_cities;
    int n_roads;
    cin >> n_cities >> n_roads;
    

    unordered_map<int, unordered_set<int>> city_map;
    unordered_map<int, int> seen_cities;     

    int road1, road2;

    for(int i = 0; i < n_roads; i++)
    {
        int temp_key;
        cin >> road1 >> road2;

        if(!seen_cities.count(road1) && !seen_cities.count(road2))
        {
            unordered_set<int> temp = {road1, road2};
            city_map[road1] = temp;
            temp_key = road1;
            seen_cities.insert({road1, temp_key});
            seen_cities.insert({road2, temp_key});
        }
        else if(seen_cities.count(road1) && city_map.count(seen_cities[road1]))
        {
            temp_key = seen_cities[road1];
            city_map[temp_key].insert(road1);
            city_map[temp_key].insert(road2);
            seen_cities.insert({road2, temp_key});
            if(seen_cities[road2] != seen_cities[road1])
            {
                unordered_set<int> to_merge = city_map[seen_cities[road2]];
                city_map.erase(seen_cities[road2]);
                unordered_set<int>::iterator it;
                for(it = to_merge.begin(); it != to_merge.end(); ++it)
                {
                    seen_cities[*it] = temp_key;
                }
                city_map[temp_key].merge(to_merge);

            }
        }
        else if(seen_cities.count(road2) && city_map.count(seen_cities[road2]))
        {
            temp_key = seen_cities[road2];
            city_map[temp_key].insert(road2);
            city_map[temp_key].insert(road1);
            seen_cities.insert({road1, temp_key});
            if(seen_cities[road2] != seen_cities[road1])
            {
                unordered_set<int> to_merge = city_map[seen_cities[road1]];
                city_map.erase(seen_cities[road1]);
                unordered_set<int>::iterator it;
                for(it = to_merge.begin(); it != to_merge.end(); ++it)
                {
                    seen_cities[*it] = temp_key;
                }
                city_map[temp_key].merge(to_merge);
            }
        }


    }
    for(int i = 1; i <= n_cities; i++)
    {
        if(!seen_cities.count(i))
        {
            city_map[i] = {i};
        }
    }
    printf("%ld\n", city_map.size() - 1);
    unordered_map<int, unordered_set<int>>::iterator it1;
    unordered_map<int, unordered_set<int>>::iterator it2 = city_map.begin();
    it2++;
    for(it1 = city_map.begin(); it2 != city_map.end(); ++it1, ++it2)
    {
        printf("%d %d\n", *(it1->second.begin()), *(it2->second.begin()));
    }

}   

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED