Connect cities

## Get adjecent cities of a city.
def getAdjecent(roadList: list[list[int]], city: int) -> list[int]:
    connections = []

    for i in range(0, len(roadList)):
        if roadList[i][0] == city:
            connections.append(roadList[i][1])
        if roadList[i][1] == city:
            connections.append(roadList[i][0])

    return connections

def getGroupings(cities: int, roads: list[list[int]]) -> list[list[int]]:
    ## Store groupings
    cityGroupings = []

    # Store unchecked cities
    uncheckedCities = []
    for i in range(1, cities + 1):
        uncheckedCities.append(i)

    # While we have cities to check.
    while(len(uncheckedCities) != 0):
        # Ini
        current = uncheckedCities[0]
        visited = []
        yetToVisit = getAdjecent(roads, current)

        # If this city is alone, just add it to list.
        if(len(yetToVisit) == 0):
            visited.append(current)

        while(len(yetToVisit) != 0):

            # Append current city and change it.
            visited.append(current)
            current = yetToVisit[0]

            # remove current one.
            yetToVisit.pop(0)

            # Add new adjecent cities that we have not been to.
            for n in getAdjecent(roads, current):
                if n not in visited and n not in yetToVisit:
                    yetToVisit.append(n)

        # Last one
        if current not in visited:
            visited.append(current)
        
        cityGroupings.append(visited)

        # Remove all of these cities from unchecked.
        for city in visited:
            if city in uncheckedCities:
                uncheckedCities.remove(city)

    return cityGroupings



# Read input
read = input().split(" ")
cityCount = int(read[0])
roadCount = int(read[1])

# Read list of roads
builtRoadArray = []
for i in range(0, roadCount):
    builtRoadArray.append(list(map(int, input().split(" "))))

print(builtRoadArray)

# Figure out groupings.
# Array of cities grouped on their connectivity.
groupedCityArray = getGroupings(cityCount, builtRoadArray)
print(groupedCityArray)

# Array of needed roads
neededRoadArray = []

# Add a new path that connects groups. Use first node in group.
## Basically just create a circle, where the last two are not connected.
for i in range(0, len(groupedCityArray) - 1):
    neededRoadArray.append([groupedCityArray[i][0], groupedCityArray[i + 1][0]])

# Output
print(len(neededRoadArray))
print(neededRoadArray)

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 12

Verdict: WRONG ANSWER