Python check if a list of nodes are all in the same connected component in O(n)

Question

I have a list of integers, call L, where each integer in that list represents a node. I also have a dictionary called G, which represents a graph in the format {node:[children]}. What I am trying to do here is to determine if all the nodes L are in the same connected component in G. For example, if L = [1, 2, 3] and G = {1:[2, 3], 2:[1], 3:[1]}, the program should output True because in this case 1, 2, and 3 are all in the same connected component. However, in the case of L = [1, 2, 3] and G = {1:[2], 2:[1], 3:[4]} the program should output False because it is not possible to reach 1 and 2 from 3 and vice versa. My question is that is such as program possible? If it is, is it possible to do it in O(n)?

I have tried googling for an answer but I have only found results on how to check if two nodes are in the same connected component, not how to check if a list of nodes is in the same connected component. Any help will be appreciated, thank you!

Answer 1

What about something like this?

def check(g):
    i = 1
    for each in g.keys():
        if each != list(g.keys())[0]:
            for childs in list(g.values()):
                if each in childs:
                    i += 1
    return i == len(g.keys())



def check(g):
    i = 1
    for each in g.keys():
        if each != list(g.keys())[0]:
            if str(each) in str(g.values()):
                i += 1
    return i == len(g.keys())