题解 | 隐匿社交网络

超时了

def find(a):    
    if p[a] != a:
        p[a] = find(p[a])   # 查找父节点
    return p[a]


def merge(a, b):    # 合并两个集合
    pa = find(a)
    pb = find(b)
    if pa != pb:
        p[pa] = pb
        si[pb] += si[pa]


while True:
    try:
        T = int(input())
        res = []
        for _ in range(T):
            n = int(input())
            w = list(map(int, input().split()))
            length = len(bin(max(w))[2:])   # 最长的二进制长度
            w = [bin(i)[2:].rjust(length, '0') for i in w]  # 权重都转换成二进制
            p = list(range(n)) # 每个节点的父节点初始化为自己
            si = [1] * n  # 每个集合的大小初始化为1
            for j in range(length):
                i = 0
                while i < n and w[i][j] == '0':
                    i += 1
                # 在该列中第一个为1的节点做集合的初始父节点
                # 如果后续还有1，将新节点合并进来做父节点，并更新集合长度
                for k in range(i+1, n): 
                    if w[k][j] == '1':
                        merge(k, i)
            ans = max(1, max(si))
            res.append(ans)
        for i in res:
            print(i)  
    except:
        break