首页 > 试题广场 >

隐匿社交网络

[编程题]隐匿社交网络
  • 热度指数：3022 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}牛客网有一个名为牛爱网神秘的入口。这天，牛可乐正在策划牛爱网的全新社交活动。
\hspace{15pt}每个人的账号在初始时都会被分配一个权重，第 i 个账号的权重为 w_i。对于任意的两个账号 i 和 j，如果权重满足 (w_i \operatorname{and} w_j) \geqq 1，那么就会被分配到同一个社交网络。
\hspace{15pt}现在，牛可乐已经为 n 个账号分配了权重，他想知道，包含账号数量最多的社交网络中，包含多少个账号。
\hspace{15pt}牛爱网的日常维护工作忙坏了牛可乐，请你帮帮他。

\hspace{15pt}其中，\operatorname{and} 表示按位与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节 。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^5\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 10^5\right) 代表账号数量。
\hspace{15pt}第二行输入 n 个整数 w_1, w_2, \dots, w_n \left(1 \leqq w_i \leqq 10^{18}\right) 代表账号权重。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 10^5 。


输出描述:
\hspace{15pt}对于每组测试数据，新起一行。输出一个整数，代表包含账号数量最多的社交网络中，包含的账号数量。
示例1

输入

2
5
2 1 6 7 16
2
2 16

输出

4
1

说明

\hspace{15pt}对于第一组测试数据，连接示意图如下图所示：
社交网络
算法知识视频讲解
添加回答
Python3
牛客348448733号头像 牛客348448733号
import sys
from collections import defaultdict
input = sys.stdin.readline

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1]*n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return
        if self.size[fx] < self.size[fy]:
            fx, fy = fy, fx
        self.parent[fy] = fx
        self.size[fx] += self.size[fy]

def get_set_bits(x):
    pos = 0
    while x:
        if x & 1:
            yield pos
        x >>= 1
        pos += 1

T = int(input())
for _ in range(T):
    n = int(input())
    w = list(map(int, input().split()))
    dsu = DSU(n)

    bit_map = defaultdict(list)
    zero_count = 0
    for i in range(n):
        if w[i] == 0:
            zero_count += 1
            continue
        for b in get_set_bits(w[i]):
            bit_map[b].append(i)

    for accounts in bit_map.values():
        root = accounts[0]
        for acc in accounts[1:]:
            dsu.union(root, acc)

    max_group = 0
    for i in range(n):
        if w[i] != 0 and dsu.find(i) == i:
            max_group = max(max_group, dsu.size[i])

    print(max(max_group, zero_count))

发表于 2025-07-28 22:40:17 回复(0)
提交观点

问题信息

并查集
难度：
1条回答 299浏览

热门推荐

相关试题

隐匿社交网络

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号