P8250 交友问题

题意简述

给定一张 $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)$$

$t$ 越大，空间越小，但时间越慢，只要在合理范围内都能通过。

参考代码

#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;
}