BZOJ 4264 小C找朋友 哈希+脑子

好吧我觉得是脑子，别人觉得是套路$qwq$

---

这道题相当于是求除了$u,v$两点互相连接，所连的点相同的点对$(u,v)$

我们首先每个点一个随机权值，对于$u$点记为$w[u]$，然后记与$u$点相连的点的异或和为$hsh[u]$

分类：

1. 若$u,v$相连，则$u,v$是朋友满足$(hsh[u]^w[v])==(hsh[v]^w[u])$；
2. 若$u,v$不相连，则$u,v$是朋友满足$hsh[u]==hsh[v]$；

对于第一种情况，直接枚举每条边上的两点就行了；对于第二种情况，先把$hsh$数组$sort$一遍，然后对于$hsh$相同的点来说，设共有$cnt$个点的$hsh[u]==c$，$c$是某定值，则答案个数是$C_{cnt}^2$。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define fr first

#define sc second

#define ull unsigned long long

#define ll long long

#define R register int

using namespace std;

namespace Fread {

    static char B[<<],*S=B,*D=B;

    #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

    inline int g() {

        R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

        do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

    }

}using Fread::g;

const int N=;

pair<int,int> e[N];

int n,m; ll ans;

ull vl[N],hsh[N];

signed main() {

#ifdef JACK

    freopen("NOIPAK++.in","r",stdin);

#endif

    n=g(),m=g(); srand();

    for(R i=;i<=n;++i) vl[i]=(ull)rand()*rand()*rand()*rand();

    for(R i=,u,v;i<=m;++i) u=e[i].fr=g(),v=e[i].sc=g(),hsh[u]^=vl[v],hsh[v]^=vl[u];

    for(R i=;i<=m;++i) ans+=(int)((hsh[e[i].fr]^vl[e[i].sc])==(hsh[e[i].sc]^vl[e[i].fr]));

    sort(hsh+,hsh+n+); R cnt=; for(R i=;i<=n;++i) {

        ++cnt; if(i==n||hsh[i]!=hsh[i+]) ans+=(ll)cnt*(cnt-)/,cnt=;

    } printf("%lld",ans);

}

---

2019.06.10