关于算法:矩阵最小广播数

2次阅读

共计 418 个字符,预计需要花费 2 分钟才能阅读完成。

def get_num(arr):

    def f(related_nodes):
        g = set()
        remain = []
        for index_g in related_nodes:
            if index_g[0] == index_g[1]:
                continue
            cur_set =set(index_g)
            if not g:
                g = cur_set
            elif g and g&cur_set:
                g = g|cur_set
            else:
                remain.append(index_g)
        return g, remain

    groups, remain_nodes = [], set(range(len(arr)))
    remain = np.argwhere(arr==1).tolist()
    while remain:
        g, remain = f(remain)
        groups.append(g)
        remain_nodes -= g
#     print(groups, remain_nodes)
    return len(groups) + len(remain_nodes)
正文完
 0