unoptimal.py

#!/bin/python3

import sys

#functions
def bsearch(x, L):
    if x == L[len(L) // 2]:
        return True
    if (len(L) // 2) == 0:
        return False
    if x > L[len(L) // 2]:
        return bsearch(x, L[ (len(L) // 2) : ])
    else:
        return bsearch(x, L[ :(len(L) // 2)])


def BFS(G, s):
    explored = []
    queue = [s]
    while queue:
        u = queue.pop()
        if u not in explored:
            explored.append(u)
            neighbours = G[u]
            for neighbour in neighbours:
                queue.append(neighbour) 
    return explored

def conn_comps(G):
    components = []
    visited = []
    conn_comp = BFS(land, list(G)[0])
    for vert in conn_comp:
        visited.append(vert)

    components.append(conn_comp)
    visited.sort()

    for k, v in land.items():
        in_vis = bsearch(k, visited)
        if not in_vis:
            comp = BFS(land, k)
            for vert in comp:
                visited.append(vert)
            components.append(comp)
    return components

land = {}

q = int(input().strip())
for a0 in range(q):
    n, m, x, y = input().strip().split(' ')
    n, m, x, y = [int(n), int(m), int(x), int(y)]
    for a2 in range(n):
        land[a2 + 1] = [] 
    for a1 in range(m):
        city_1, city_2 = input().strip().split(' ')
        city_1, city_2 = [int(city_1), int(city_2)]
        
        #insertar ciudades en el grafo
        if city_1 in land:
            if not land[city_1]:
                land[city_1] = []
                land[city_1].append(city_2)
            else:
                land[city_1].append(city_2)
        else:
            land[city_1] = []
            land[city_1].append(city_2)
            
        if city_2 in land:
            if not land[city_2]:
                land[city_2] = []
                land[city_2].append(city_1)
            else:
                land[city_2].append(city_1)
        else:
            land[city_2] = []
            land[city_2].append(city_1)
    
    if y >= x:
        print(n * x)
    else:
        towns = []
        #find the connected components if any, save it in towns
        towns = conn_comps(land)
        n_libs = 0
        n_roads = 0
        n_towns = len(towns)
        for town in towns:
            n_roads = n_roads + (len(town) - 1)

        print((n_roads * y) + (x * n_towns))

    land = {}