题解 | 隐匿社交网络

建图，定义62个虚点，分别表示第i位上是否是1，然后遍历所有数，将其连向对应的虚点。

最后进行dfs即可。

需要注意的一个细节是虚点不能被计入答案，需要减去这部分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N = 2e5+9;
int const inf = 1e9+7;
int n;
int w[N];
vector<int> v[N];
int vis[N];
int tot = 0,ans = 0;
int p(int j)
{
	return n + j + 1;
}

void dfs(int x)
{
	tot++;
	vis[x] = 1;
	for(auto to : v[x])
	{
		if(vis[to]) continue;
		dfs(to);
	}
	return;
}

void solve()
{
	tot = ans = 0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=62;j++)
		{
			if((w[i] >> j) & 1)
			{
				int b = p(j);
				v[b].push_back(i);
				v[i].push_back(b);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;
		dfs(i);
		for(int j=0;j<=62;j++)
		{
			if(vis[p(j)])
			{
				tot--;
				vis[p(j)] = 0;
			}
		}
		ans = max(ans,tot);
		tot = 0;
		
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) v[i].clear(),vis[i] = 0;
	for(int j=0;j<=62;j++) vis[p(j)] = 0,v[p(j)].clear();
	return;
}
signed main()
{
	int T;cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

/*
1 1
2 2 + 1
3 3 + 2 +1

*/