题解：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

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

参考代码

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

题解：P8250 交友问题

文章操作

题意简述

解题思路

参考代码

相关推荐

评论

题解：P8250 交友问题