[CF1468M] Similar Sets - 根号分治
Description
两个集合的交大小不小于 2 称为相似集合。给定若干个集合,输出任意一对相似集合,或者判定无解。
Solution
设 m 为总数,令 D=sqrt(m),将至少具有 D 个元素的集合称为大集合,否则称为小集合。
首先,我们检查是否有大集合与其它集合相似。枚举每一个大集合 S,我们试图为他找一个相似集合,我们设置 \(w[x]=1\),然后将其它所有集合的所有元素扫一遍。
现在我们需要检查是否有两个小集合相似。对于每个小集合,我们枚举其中所有的 (x,y) 有序对,然后我们检查是否有来自不同集合的相同有序对。
每部分的复杂度都是 O(m sqrt(m))。
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<vector<int>> s(n + 2);
map<int, int> mp;
int total = 0;
for (int i = 1; i <= n; i++)
{
int m;
cin >> m;
s[i].resize(m + 2);
s[i][0] = m;
for (int j = 1; j <= m; j++)
cin >> s[i][j], mp[s[i][j]]++;
total += m;
}
int ind = 0;
for (auto &[x, y] : mp)
y = ++ind;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= s[i][0]; j++)
s[i][j] = mp[s[i][j]];
}
int sq = sqrt(total / 16);
vector<int> use(ind + 2);
// Big - big/small
for (int i = 1; i <= n; i++)
{
if (s[i][0] < sq)
continue;
for (int j = 1; j <= s[i][0]; j++)
use[s[i][j]] = 1;
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
int cnt = 0;
for (int k = 1; k <= s[j][0]; k++)
if (use[s[j][k]])
++cnt;
if (cnt >= 2)
{
cout << i << " " << j << endl;
return;
}
}
for (int j = 1; j <= s[i][0]; j++)
use[s[i][j]] = 0;
}
// Small-small
vector<tuple<int, int, int>> vec;
for (int i = 1; i <= n; i++)
{
if (s[i][0] >= sq)
continue;
for (int j = 1; j <= s[i][0]; j++)
{
for (int k = j + 1; k <= s[i][0]; k++)
{
vec.push_back({s[i][j], s[i][k], i});
}
}
}
vector<vector<pair<int, int>>> g(ind + 2);
for (auto [x, y, z] : vec)
{
if (x < y)
g[x].push_back({y, z});
else
g[y].push_back({x, z});
}
vector<int> from(ind + 2);
// For same first value
for (int i = 1; i <= ind; i++)
{
// check if same second value in different set
for (auto [x, y] : g[i])
{
if (from[x] == 0)
from[x] = y;
else
{
cout << from[x] << " " << y << endl;
return;
}
}
for (auto [x, y] : g[i])
from[x] = 0;
}
cout << -1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
}