隐匿社交网络

#include <bits/stdc++.h>
using namespace std;

vector<long long> father(64);

int Find(int u) {
    if (father[u] == u) return u;
    father[u] = Find(father[u]);
    return father[u];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;
    else father[a] = b;
}

int main() {
    long long n;
    cin >> n;
    while (n--) {
        long long m, ans = 0;
        cin >> m;

        vector<vector<int>> index(64);
        vector<long long> w(m);
        for (int i = 0; i < 64; i++) {
            father[i] = i;
        }

        for (int i = 0; i < m; i++) {
            cin >> w[i];
            vector<long long> temp;
            
            for (int j = 0; j < 64; j++) {
                if ((w[i] >> j) & 1) {
                    index[j].push_back(i);
                    temp.push_back(j);
                }
            }
            
            if (temp.size() > 1) {
                for (int i = 1; i < temp.size(); i++) {
                    Union(temp[i - 1], temp[i]);
                }
            }
        }

        for (int i = 0; i < 64; i++) {
            if (father[i] != i) {
                for (int j = 0; j < index[i].size(); j++) {
                    index[father[i]].push_back(index[i][j]);
                }
                sort(index[father[i]].begin(), index[father[i]].end());
            }
        }

        for (int i = 0; i < 64; i++) {
            long long cnt = 1;
            for (int j = 1; j < index[i].size(); j++) {
                if (index[i][j] != index[i][j - 1]) {
                    cnt++;
                }
            }
            ans = max(ans, cnt);
        }

        cout << ans << endl;
    }

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    /**
     * 合并社交圈，计算最大社交圈的大小
     * 使用位运算表示用户的兴趣标签，通过或运算合并有共同兴趣的社交圈
     * 
     * @param interests 每个用户的兴趣标签数组（用long的二进制位表示）
     * @param userCount 用户数量
     */
    public static void mergeSocialCircles(long[] interests, int userCount) {
        // 使用Map表示社交圈：key为社交圈的标签（所有用户兴趣的或运算结果），value为该社交圈的用户数量
        Map<Long, Integer> socialCircles = new HashMap<>();
        int maxCircleSize = 0; // 记录最大社交圈的大小
        
        for (int i = 0; i < userCount; i++) {
            long currentInterest = interests[i];
            long mergedInterest = currentInterest; // 合并后的兴趣标签
            int mergedCount = 1; // 合并后的用户数量，初始为当前用户自己
            
            // 遍历现有社交圈，查找与当前用户有共同兴趣的圈子
            // 注意：这里使用临时数组来避免在遍历时修改Map
            Long[] existingCircles = socialCircles.keySet().toArray(new Long[0]);
            
            for (Long circleInterest : existingCircles) {
                // 检查当前用户兴趣与社交圈兴趣是否有交集（按位与结果不为0）
                if ((currentInterest & circleInterest) != 0) {
                    // 合并兴趣标签（按位或）
                    mergedInterest |= circleInterest;
                    // 累加用户数量
                    mergedCount += socialCircles.get(circleInterest);
                    // 移除被合并的社交圈
                    socialCircles.remove(circleInterest);
                }
            }
            
            // 将合并后的社交圈加入Map
            socialCircles.put(mergedInterest, mergedCount);
            // 更新最大社交圈大小
            maxCircleSize = Math.max(maxCircleSize, mergedCount);
        }
        
        System.out.println(maxCircleSize);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取测试用例数量
        int testCaseCount = scanner.nextInt();
        
        for (int i = 0; i < testCaseCount; i++) {
            // 读取当前测试用例的用户数量
            int userCount = scanner.nextInt();
            long[] interests = new long[userCount];
            
            // 读取每个用户的兴趣标签
            for (int j = 0; j < userCount; j++) {
                interests[j] = scanner.nextLong();
            }
            
            // 处理当前测试用例
            mergeSocialCircles(interests, userCount);
        }
        
        scanner.close();
    }
}