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

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

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

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

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

社交网络 1 是 {3,4}

老实说，我对如何启动这个程序一头雾水，如有任何提示，我们将不胜感激。

请您参考如下方法:

可用于解决此问题的一种有效数据结构是不相交集，也称为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))