Connect cities

# def dfs(city, cityMappingDict, visited):
#   visited.add(city)
#   for neighbour in cityMappingDict[city]:
#     if neighbour not in visited:
#       dfs(neighbour, cityMappingDict, visited)

# def find_num_graphs(cityMappingDict, n):
#   visited = set()
#   graphCount = 0

#   # iterate through all cities
#   for city in range(1, n + 1):
#     if city not in visited:
#       dfs(city, cityMappingDict, visited)
#       graphCount += 1

#   return graphCount

def findRoadsToBuild(cityMappingDict, n):
  graphs = []
  visited = set()

  for city in range(1, n + 1):
    if city not in visited:
      graph = []
      dfs2(city, cityMappingDict, visited, graph)
      graphs.append(graph)

  # print("Graphs:", graphs)

  roadsToBuildList = []
  for i in range(len(graphs) - 1):
    roadsToBuildList.append((graphs[i - 1][0], graphs[i][0]))

  return roadsToBuildList

def dfs2(city, cityMappingDict, visited, graph):
  visited.add(city)
  graph.append(city)
  for neighbour in cityMappingDict[city]:
    if neighbour not in visited:
      dfs2(neighbour, cityMappingDict, visited, graph)


# first line, n (number of cities) and m (number of roads)
numCitiesNumRoadsInput = input().split()
n = int(numCitiesNumRoadsInput[0])
m = int(numCitiesNumRoadsInput[1])

# initialise dict to act as an adjacency list
cityMappingDict = dict()

# subsequent lines, roads connecting cities
for i in range(m):
  cityRoadConnectionString = input().split()
  leftCity = int(cityRoadConnectionString[0])
  rightCity = int(cityRoadConnectionString[1])
  leftCityList = cityMappingDict.get(leftCity, [])
  leftCityList.append(rightCity)
  cityMappingDict[leftCity] = leftCityList

  rightCityList = cityMappingDict.get(rightCity, [])
  rightCityList.append(leftCity)
  cityMappingDict[rightCity] = rightCityList

# print(cityMappingDict)

# find number of graphs
# graphsCount = find_num_graphs(cityMappingDict, n)

# print(graphsCount)

newRoads = findRoadsToBuild(cityMappingDict, n)

print(len(newRoads))

print(newRoads)

Test 1

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 2

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 3

Verdict: ACCEPTED

Test 4

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 5

Verdict: ACCEPTED

Test 6

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 10

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 11

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 73, in <module>
    n...