P8250 交友问题
P8250 交友问题https://www.luogu.com.cn/problem/P8250
题面描述:
一个有n个点m条边的无向简单图
每次询问u,v,问与u相邻且不为v的点中有多少个的点不与v相邻
题解:
正难则反,我们考虑有多少个点为v或与v相邻,在用u.size()减去即可
首先,让我们抛弃大O,先来思考暴力,
暴力1:我们对每个点开一个bitset,每次询问直接返回两个bitset相与的结果,时间复杂度
暴力2:我们开一个桶,每次将v的所以邻居加入桶,再用计算其中u的邻居的出现次数时间复杂度O(nq)
正解:
考虑将他们融合,根号分治!!!
设置一个阈值T,将入度大于T的称为重点,入度小于等于T的称为轻点
因为图中一共只有2m个入度,所以当我们将阈值T设为sqrt(2m)时,即可将重点个数定为根号级
分四种情况讨论
1.(重,重) 采用暴力1的做法,
2.(轻,轻) 采用暴力2的做法,
3.(重,轻) 枚举轻点的邻居,利用重点的bitsetO(1)判断,
4.(轻,重) 与情况3相同,
在T取时,情况1时间复杂度仍为
,较为危险,容易别卡常,
因此考虑面向数据编程
我们开桶记录答案,使答案变为,即
,于是将T开大一点,实测T=1000可过
其实不加也可以
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,q,rd[N],cnt,anss[1100][1100];
vector<int>a[N];
bitset<N>vis[1100];
bool mp[N];
int main()
{memset(anss,-1,sizeof(anss));scanf("%d%d%d",&n,&m,&q);int k=1000;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}for(int i=1;i<=n;i++){if(a[i].size()<=k) continue;rd[i]=++cnt;vis[cnt][i]=1;for(auto it:a[i]) vis[cnt][it]=1;}while(q--){int x,y,ans=0;scanf("%d%d",&x,&y);if(x==y){printf("0\n");continue;}if(a[x].size()>k&&a[y].size()>k){if(anss[rd[x]][rd[y]]!=-1) ans=anss[rd[x]][rd[y]];else ans=anss[rd[x]][rd[y]]=(vis[rd[x]]&vis[rd[y]]).count()-(vis[rd[x]][y]);}if(a[x].size()>k&&a[y].size()<=k){for(auto it:a[y]) if(vis[rd[x]][it]) ans++;}if(a[x].size()<=k&&a[y].size()>k){for(auto it:a[x]) if(vis[rd[y]][it]) ans++;}if(a[x].size()<=k&&a[y].size()<=k){mp[y]=1;for(auto it:a[y]) mp[it]=1;for(auto it:a[x]) ans+=mp[it];for(auto it:a[y]) mp[it]=0;mp[y]=0;}printf("%d\n",a[x].size()-ans);}return 0;
}