python - 在python中创建认识其他 friend 的 friend 字典

Question

在任何一群人中，都有很多对 friend 。假设有一个 friend 的两个人本身就是 friend 。 (是的，这在现实生活中是一个不切实际的假设，但我们还是这么做吧)。换句话说，如果A和B是 friend ，B和C是 friend ，那么A和C也一定是 friend 。使用这条规则，只要我们了解一些关于该群体中的友谊的信息，我们就可以将任何一群人划分为 friend 圈。

编写一个带有两个参数的函数networks()。第一个参数是群组中的人数，第二个参数是定义 friend 的元组对象列表。假设人们由数字 0 到 n-1 来标识。例如，元组 (0, 2) 表示人 0 是人 2 的 friend 。该函数应该打印人员划分为 friend 圈的情况。下面显示了该函数的几个示例运行:

>>>networks(5,[(0,1),(1,2),(3,4)])#execute

社交网络 0 是 {0,1,2}

社交网络 1 是 {3,4}

老实说，我对如何启动这个程序感到非常困惑，任何提示将不胜感激。

Answer 1

可用来解决此问题的一种有效数据结构是不相交集，也称为union-find 结构。不久前我为 another answer 写了一篇.

结构如下:

class UnionFind:
    def __init__(self):
        self.rank = {}
        self.parent = {}

    def find(self, element):
        if element not in self.parent: # leader elements are not in `parent` dict
            return element
        leader = self.find(self.parent[element]) # search recursively
        self.parent[element] = leader # compress path by saving leader as parent
        return leader

    def union(self, leader1, leader2):
        rank1 = self.rank.get(leader1,1)
        rank2 = self.rank.get(leader2,1)

        if rank1 > rank2: # union by rank
            self.parent[leader2] = leader1
        elif rank2 > rank1:
            self.parent[leader1] = leader2
        else: # ranks are equal
            self.parent[leader2] = leader1 # favor leader1 arbitrarily
            self.rank[leader1] = rank1+1 # increment rank

以下是如何使用它来解决您的问题:

def networks(num_people, friends):
    # first process the "friends" list to build disjoint sets
    network = UnionFind()
    for a, b in friends:
        network.union(network.find(a), network.find(b))

    # now assemble the groups (indexed by an arbitrarily chosen leader)
    groups = defaultdict(list)
    for person in range(num_people):
        groups[network.find(person)].append(person)

    # now print out the groups (you can call `set` on `g` if you want brackets)
    for i, g in enumerate(groups.values()):
        print("Social network {} is {}".format(i, g))