Connect cities

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>

// def addSubItems(curItem, listIndex, roadsSetList, roadDict, checkedDict):
// #print("Checking", curItem)
//     if checkedDict[curItem] != -1:
//         return 0
//     checkedDict[curItem] = listIndex
//     if len(roadsSetList) <= listIndex:
// #roadsSetList += [set() for _ in range(10)]
//         roadsSetList.append(set())

//     if curItem in roadDict:
//         roadsSetList[checkedDict[curItem]].update(roadDict[curItem])
//     else:
//         roadsSetList[checkedDict[curItem]] = set([curItem])
//         return 1

//     for oneRoad in roadDict[curItem]:
//         if checkedDict[oneRoad] != -1:
//             continue
//         addSubItems(oneRoad, listIndex, roadsSetList, roadDict, checkedDict)
//     return 1
int addSubItems(int curItem, int listIndex,
                std::vector<std::set<int>> &roadsSetList,
                std::unordered_map<int, std::set<int>> &roadDict,
                std::vector<int> &checkedDict) {
  if (checkedDict[curItem] != -1) {
    return 0;
  }
  checkedDict[curItem] = listIndex;
  if (roadsSetList.size() <= (long unsigned int)listIndex) {
    std::set<int> kk;
    roadsSetList.push_back(kk);
  }
  if (roadDict.contains(curItem)) {
    // roadsSetList[checkedDict[curItem]].update(roadDict[curItem]);
    roadsSetList[checkedDict[curItem]].insert(roadDict[curItem].begin(),
                                              roadDict[curItem].end());
  } else {
    roadsSetList[checkedDict[curItem]] = std::set({curItem});
    return 1;
  }
  for (int oneRoad : roadDict[curItem]) {
    if (checkedDict[oneRoad] != -1) {
      continue;
    }
    addSubItems(oneRoad, listIndex, roadsSetList, roadDict, checkedDict);
  }

  return 1;
}

template <typename T>
std::ostream &operator<<(std::ostream &out, const std::set<T> &set) {
  if (set.empty())
    return out << "{}";
  out << "{ " << *set.begin();
  std::for_each(std::next(set.begin()), set.end(),
                [&out](const T &element) { out << ", " << element; });
  return out << " }";
}
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &set) {
  if (set.empty())
    return out << "[]";
  out << "[ " << *set.begin();
  std::for_each(std::next(set.begin()), set.end(),
                [&out](const T &element) { out << ", " << element; });
  return out << " ]";
}
template <typename T>
std::ostream &operator<<(std::ostream &out,
                         const std::unordered_map<T, std::set<int>> &set) {
  if (set.empty())
    return out << "{}";
  out << "{ ";
  for (const auto &[key1, value1] : set) {
    std::cout << key1 << ": " << value1 << std::endl;
  }
  return out << " }";
}

int main() {

  char debug = 0;
  int cities = 0;
  int roads = 0;

  std::cin >> cities;
  std::cin >> roads;
  // std::cout << count << " " << carCount << std::endl;
  //   std::cout << count << std::endl;
  //   std::cout << cityCount << " " << roadCount << std::endl;
  std::vector<int> alreadyRoads(roads * 2);
  for (int ii = 0; ii < roads * 2; ii += 2) {
    int city1;
    std::cin >> city1;
    alreadyRoads[ii] = city1 - 1;
    int city2;
    std::cin >> city2;
    alreadyRoads[ii + 1] = city2 - 1;
  }

  if (debug)
    std::cout << alreadyRoads << std::endl;

  std::unordered_map<int, std::set<int>> roadDict;
  for (long unsigned int ii = 0; ii < alreadyRoads.size(); ii += 2) {
    int start = alreadyRoads[ii];
    int end = alreadyRoads[ii + 1];

    if (roadDict.contains(start)) {
      roadDict[start].insert(end);
    } else {
      roadDict[start] = std::set<int>{end};
    }
    if (roadDict.contains(end)) {
      roadDict[end].insert(start);
    } else {
      roadDict[end] = std::set<int>{start};
    }
  }
  if (debug)
    std::cout << roadDict << std::endl;
  std::vector<int> checkedDict(cities, -1);
  std::vector<std::set<int>> roadsSetList;
  int counter = 0;
  for (int ii = 0; ii < cities; ii++) {
    int ids = checkedDict[ii];
    if (ids != -1) {
      continue;
    }
    counter += addSubItems(ii, counter, roadsSetList, roadDict, checkedDict);
  }
  if (debug)
    std::cout << checkedDict << std::endl;
  if (debug)
    std::cout << roadsSetList << std::endl;

  // for ii in range(1, len(roadsSetList)):
  // cur = 0
  // for aa in roadsSetList[ii]:
  // cur = aa
  // break
  // print(zeroth + 1, cur + 1)
  std::cout << roadsSetList.size() - 1 << std::endl;
  std::set<int>::iterator firstIt = roadsSetList[0].begin();
  int first = *(firstIt);
  for (long unsigned int ii = 1; ii < roadsSetList.size(); ii++) {
    std::set<int>::iterator it = roadsSetList[ii].begin();
    std::cout << first + 1 << " " << *(it) + 1 << std::endl;
  }

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED