ECNU 3337 我认识你 (思维)

Description

人与人之间的关系错综复杂,常常会出现一个叫作共同好友的东西。所以,贴心的 QQ 就提供了这样一个功能,可以显示你与某人(不一定是好友)有多少个共同好友。但是,当用户量逐渐增大,好友关系网不断复杂化,共同好友计算的效率就变得十分重要了。

你刚刚和腾讯公司签约,获得了共同好友计算的开发资格。

 

Input

第一行有两个整数 $n,m (1≤n≤40~000,1≤m≤40~000)$ 。分别表示用户数量和好友关系数量。方便起见,用户编号为 $1$ 到 $n$。

接下来 $m$ 行,每行两个整数用空格隔开 $u,v (1≤u,v≤n,u≠v)$,表示 $u$ 和 $v$ 是好友。数据保证不会出现两对相同的 $u,v$。

接下来一行一个整数 $q (1≤q≤40~000)$ 表示查询数。

接下来 $q$ 行,每行两个整数 $s,t (1≤s,t≤n,s≠t)$,表示询问的对象。

 

Output

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

 

Examples input

3 3
1 2
1 3
3 2
2
1 3
3 2

 

Examples output

1
1

 

思路

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

不过伤心的是,点的个数最大有 $4e4$ ,我们无法承受 $O(n^2)$ 的复杂度,因此便需要考虑其他的优化办法了。


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

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

显然,我们想要求出点 $i$ 与点 $j$ 的共同好友只需要计算 $G[i]\&G[j]$ 二进制中 $1$ 的个数。

另外还需要用到 GCC 内置的神器:__builtin_popcountll 函数,它可以很高效的计算出 long long 整数二进制中 $1$ 的个数。

 

AC 代码

#include<bits/stdc++.h>
#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<<low;
}

int union_set(int u,int v)
{
    int ans = 0;
    for(int i=0; i<maxm; i++)
    {
        tmp[i] = G[u][i] & G[v][i];
        ans += __builtin_popcountll(tmp[i]);
    }
    return ans;
}

int main()
{
    IO;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int u,v;
        cin>>u>>v;
        set_id(u,v);
        set_id(v,u);
    }
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        cout<<union_set(u,v)<<endl;
    }
    return 0;
}

  • 4 只已被捕捉
    • godweiyang Mozilla FireFox | 59.0 Windows 10

      666,我暴力过了八九十分就放弃了

      • 千千 Chrome | 65.0.3325.181 Windows 10

        虽然我也差不多是暴力的,哈哈~

    • lsx Apple Safari | 604.1 iPhone 11_2_6

      膜拜千神

      • 千千 Chrome | 65.0.3325.181 Windows 10

        膜拜 lsx dalao o(* ̄︶ ̄*)o