python - 检查两个人是否通过 friend 联系

Question

每个子列表都意味着他们是 friend ，现在我想创建一个函数 def is_connected_via_friendships_with 来检查他们是否通过与另一个人的友谊联系在一起。例如，玛丽是卢卡斯的 friend 。她和彼得是 friend ，彼得和朱莉是 friend 。因此该函数需要为 Marie 和 Julie 返回 True。另请注意，我不能为此使用 import。提前谢谢你。

network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma', 'Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'], ['Suzy', 'Tobias']]}
print (is_connected_via_friendships_with(network, 'Marie', 'Julie')) # true
print (is_connected_via_friendships_with(network, 'Julie', 'Tobias')) # false
print (is_connected_via_friendships_with(network, 'Julie', 'Frank'))  # false

Answer 1

基本上，您必须找出两个 friend 是否位于图中的相同连通分量中。检查 2 个节点是否位于同一连接组件中的多种方法。您可以使用不相交集来优化此问题的实现。从 Here 使用的不相交集实现

代码如下:

class DisjointSet:
    def __init__(self, vertices, parent):
        self.vertices = vertices
        self.parent = parent

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            return self.find(self.parent[item])

    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)
        self.parent[root1] = root2

    def is_in_same_set(self, fa, fb):
        return self.find(fb) == self.find(fa)

def get_vertices(network):
    myset = set()
    for a,b in network['friendships']:
        myset.add(a)
        myset.add(b)
    return list(myset)


def is_connected_via_friendships_with(network, fa,fb):
    return network.is_in_same_set(fa,fb)

def main():

    network = {'friendships' :[['Marie', 'Lucas'], ['Lucas', 'Patsy'], ['Emma','Lucas'], ['Emma', 'Kevin'], ['Peter', 'Emma'], ['Peter', 'Lucas'], ['Peter', 'Julie'],     ['Suzy', 'Tobias']]}

    vertices = get_vertices(network)
    parent = {}

    for v in vertices:
        parent[v] = v

    ds = DisjointSet(vertices, parent)

    for a,b in network['friendships']:
        ds.union(a,b)

    print(is_connected_via_friendships_with(ds, 'Marie', 'Julie'))
    print(is_connected_via_friendships_with(ds, 'Peter', 'Suzy'))
main()

输出为:

True
False