ECNU 3337 我认识你 （思维）

ECNU 3337 我认识你 （思维）

Description

人与人之间的关系错综复杂，常常会出现一个叫作共同好友的东西。所以，贴心的 就提供了这样一个功能，可以显示你与某人（不一定是好友）有多少个共同好友。但是，当用户量逐渐增大，好友关系网不断复杂化，共同好友计算的效率就变得十分重要了。你刚刚和腾讯公司签约，获得了共同好友计算的开发资格。

Input

第一行有两个整数 n,m(1≤n≤40 000,1≤m≤40 000) n , m ( 1 ≤ n ≤ 40   000 , 1 ≤ m ≤ 40   000 ) 。分别表示用户数量和好友关系数量。方便起见，用户编号为 1 1 到 nn。接下来 m m 行，每行两个整数用空格隔开 u,v(1≤u,v≤n,u≠v)u,v(1≤u,v≤n,u≠v)，表示 u u 和 vv 是好友。数据保证不会出现两对相同的 u,v u , v 。接下来一行一个整数 q(1≤q≤40 000) q ( 1 ≤ q ≤ 40   000 ) 接下来 q q 行，每行两个整数 s,t(1≤s,t≤n,s≠t)s,t(1≤s,t≤n,s≠t)，表示询问的对象。

Output

对于每组询问，输出这两个人有多少个共同好友。

Examples input

3 31 21 33 221 33 2

Examples output

11

思路

按照常规的做法，我们一定会首先建立好好友之间关系的无向图，然后针对每一条询问查询这两点邻接点的交集，交集的大小即为共同好友的数目。

不过伤心的是，点的个数最大有 4e4 4 e 4 ，我们无法承受 O(n2) O ( n 2 )

感觉千千这道题是暴力水过去的欸~

我们把图的邻接矩阵压缩到 40000×625 40000 × 625 的 ​​long long​​ 数组中，则整数的二进制位代表相应的边。

显然，我们想要求出点 i i 与点 jj 的共同好友只需要计算 G[i]&G[j] G [ i ] & G [ j ] 二进制中 1 1

另外还需要用到 GCC 内置的神器：​​__builtin_popcountll​​​ 函数，它可以很高效的计算出 ​​long long​​ 整数二进制中 11

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 4e4+10;const int maxm = maxn >> 6;int n,m,q;LL G[maxn][maxm];LL tmp[maxm];void set_id(int u,int v){ --v; int axis = v >> 6; int low = v & ((1 << 6) - 1); G[u][axis] |= 1LL<>n>>m; for(int i=0; i>u>>v; set_id(u,v); set_id(v,u); } cin>>q; while(q--) { int u,v; cin>>u>>v; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。