题解：P8250 交友问题
lailai0916
·
·
题解
题意简述
给定一张 n 个节点 m 条无向边的好友关系图，有 q 次询问 u 的好友中不认识 v 的数量。（n,q\le 2\times 10^5,m\le 7\times 10^5）
解题思路
设 u 的好友集合为：
N(u)=\set{v\in V|(u,v)\in E}
题目询问：
|N(u)\setminus(N(v)\cup\set{v})|
考虑暴力实现：可以 O(m) 预处理 n\times n 的数组存储邻接矩阵，每次询问 O(n) 枚举所有好友。
T=O(m+qn),M=O(n^2)
考虑时间优化：可以用 bitset 存储邻接矩阵，每次询问将两行按位与，统计其中 1 的个数。
T=O\left(m+\frac{qn}{w}\right),M=O\left(\frac{n^2}{w}\right)
考虑空间优化：可以不预处理邻接矩阵，而在每次询问时现场计算。
T=O(m+qn),M=O(m+n)
结合这两种优化方法，可以将度数大于阈值 t 的点预处理，其他的点现场计算。
由于有 m 条边，所有点的总度数为 2m，所以预处理点不超过 \frac{2m}{t} 个。
T=O\left(m+\frac{mn}{tw}+q\left(\frac{n}{w}+t\right)\right),M=O\left(m+\frac{mn}{tw}\right)
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
vector<int> G[N];
map<int,bitset<N>> a;
int in[N];
bitset<N> build(int u)
{
bitset<N> res;
for(auto v:G[u])res[v]=1;
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,q;
cin>>n>>m>>q;
while(m--)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
in[u]++;in[v]++;
}
for(int i=1;i<=n;i++)
{
if(in[i]>1000)a[i]=build(i);
}
while(q--)
{
int u,v;
cin>>u>>v;
auto x=a.find(u)!=a.end()?a[u]:build(u);
auto y=a.find(v)!=a.end()?a[v]:build(v);
y[v]=1;
cout<<(x&~y).count()<<'\n';
}
return 0;
}
```