graph_problem

gistfile1.txt

#!/bin/python3

import sys


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

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 a1 in range(m):
        city_1, city_2 = input().strip().split(' ')
        city_1, city_2 = [int(city_1), int(city_2)]
        #print(city_1, 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] = []
    
    first = True
    towns = []    
    for k, v in land.items():
        if first:
            towns.append(BFS(land, k))
            first = False
        print(k, BFS(land, k)) 
        if k not in BFS(land, k - 1 ):
            first = True
    print(towns)
        
        
    #print(land )

land = {}