题解 CF1468M【Similar Sets】
whiteqwq
·
·
题解
CF1468M Similar Sets解题报告：
更好的阅读体验
题意
定义两个集合相似当且仅当这两个集合有至少两个相同的元素，给定若干个集合，输出一对相似集合或者报告无解。
## 分析
下面设 $m=\sum|S|$。
看到 2e5 考虑根号分治，设集合大小大于 $\sqrt m$ 的点为大集合，其余为小集合，那么对于每个大集合，我们标记它所有元素，并枚举每个集合判断，由于大集合只会有根号个，所以复杂度是 $O(m\sqrt m)$ 的。
对于每个小集合，我们枚举其中两个元素并记录下来，然后判断有没有重复的点对，精细实现以下就是 $O(m\sqrt m)$。（具体就是固定第一维，第二维用桶统计）
## 代码
实现需要精细一点，否则会爆空间。
```
#include<stdio.h>
#include<vector>
#include<map>
#include<math.h>
using namespace std;
const int maxn=100005,maxm=200005;
int T,n,m,B,x,y,tot,flg;
int vis[maxm];
vector<int>v[maxn];
vector< pair<int,int> >w[maxm];
map<int,int>mp;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n),mp.clear(),m=x=y=tot=flg=0;
for(int i=1,k;i<=n;i++){
scanf("%d",&k),m+=k,v[i].clear();
for(int j=0,x;j<k;j++){
scanf("%d",&x);
if(mp[x]==0)
mp[x]=++tot,vis[tot]=0,w[tot].clear();
x=mp[x],v[i].push_back(x);
}
}
B=sqrt(m)/2;
for(int i=1;i<=n;i++){
if(v[i].size()>B){
for(int j=0;j<v[i].size();j++)
vis[v[i][j]]=1;
for(int j=1;j<=n;j++){
if(j==i)
continue;
int cnt=0;
for(int k=0;k<v[j].size();k++)
cnt+=vis[v[j][k]];
if(cnt>=2){
flg=1,printf("%d %d\n",i,j);
break;
}
}
for(int j=0;j<v[i].size();j++)
vis[v[i][j]]=0;
}
if(flg)
break;
}
if(flg)
continue;
for(int i=1;i<=n;i++)
if(v[i].size()<=B)
for(int j=0;j<v[i].size();j++)
for(int k=j+1;k<v[i].size();k++)
w[min(v[i][j],v[i][k])].push_back(make_pair(max(v[i][j],v[i][k]),i));
for(int i=1;i<=tot;i++){
for(int j=0;j<w[i].size();j++){
if(vis[w[i][j].first]){
flg=1,printf("%d %d\n",vis[w[i][j].first],w[i][j].second);
break;
}
vis[w[i][j].first]=w[i][j].second;
}
if(flg==1)
break;
for(int j=0;j<w[i].size();j++)
vis[w[i][j].first]=0;
}
if(flg==0)
puts("-1");
}
return 0;
}
```