Python 检查节点列表是否都在 O(n) 的同一个连接组件中

Question

我有一个整数列表，称为 L，其中该列表中的每个整数代表一个节点。我还有一本名为 G 的字典，它表示格式为 {node:[children]} 的图形。我在这里要做的是判断所有节点L是否在G中的同一个连通分量中。例如，如果L = [1, 2, 3]和G = {1:[2, 3], 2:[1], 3:[1]}，程序应该输出True，因为在这种情况下，1、2 和 3 都在同一个连通分量中。但是，在 L = [1, 2, 3] 和 G = {1:[2], 2:[1], 3:[4]} 的情况下，程序应该输出 False 因为不可能从 3 到达 1 和 2，反之亦然。我的问题是这样的程序可能吗？如果是，是否可以在 O(n) 内完成？

我曾尝试使用谷歌搜索寻找答案，但我只找到了关于如何检查两个节点是否在同一个连通分量中的结果，而不是如何检查节点列表是否在同一个连通分量中的结果。任何帮助将不胜感激，谢谢！

Answer 1

这样的事情怎么样？

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())

Python 检查节点列表是否都在 O(n) 的同一个连接组件中

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

python

python-3.x

python-3.7

connected-components