题解 | 隐匿社交网络 并查集做法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class UnionFind{
        int[] parent;
        int[] size;
        int maxSize;
        public UnionFind(int n){
            int total=n+61;
            parent=new int[total];
            size=new int[total];
            maxSize=1;
            for(int i=0;i<total;i++){
                parent[i]=i;
                size[i]=(i<n)?1:0;
            }
        }
        public int find(int x){
            if(parent[x]!=x){
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        public void union(int x,int y){
            int rootX=find(x);
            int rootY=find(y);
            if(rootX==rootY) return;
            if(size[rootX]<size[rootY]){
                int temp=rootX;
                rootX=rootY;
                rootY=temp;
            }
            parent[rootY]=rootX;
            size[rootX]+=size[rootY];
            maxSize=Math.max(maxSize,size[rootX]);
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            long[] weights=new long[n];
            for(int i=0;i<n;i++)
            {weights[i]=in.nextLong();
            //System.out.print(weights[i]+" ");
            }
            UnionFind uf=new UnionFind(n);
            for(int i=0;i<n;i++){
                long w=weights[i];
                for(int bit=0;bit<=60;bit++){
                    if((w&(1L<<bit))!=0){
                        uf.union(i,n+bit);
                    }
                }
            }
            System.out.println(uf.maxSize);
        }
    }
}