「bzoj4264 小C找朋友」

就是一个集合\(hash\)

集合\(hash\)可以用于判断两个集合是否相等，具体做法就是给每个随机一个值，之后异或起来就是可以了

这个题就是这样，处理出每个点直接相连的点集的\(hash\)值，之后判断一下有多少对\(hash\)值相等就好了

在考虑一下每条边就做完了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<ctime>

#include<map>

#define maxn 1000005

#define re register

#define LL unsigned long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int u[maxn],v[maxn];

int n,m;

LL a[maxn],s[maxn];

std::map<LL,int> ma;

int main()

{

	n=read(),m=read();

	srand(time(0));

	for(re int i=1;i<=n;i++) a[i]=((LL)(((LL)rand()<<15ll)*((LL)rand()<<12ll))^(LL)rand());

	for(re int i=1;i<=m;i++) u[i]=read(),v[i]=read(),s[u[i]]^=a[v[i]],s[v[i]]^=a[u[i]];

	LL ans=0;

	for(re int i=1;i<=n;i++) ans+=ma[s[i]],ma[s[i]]++;

	for(re int i=1;i<=m;i++) if((s[u[i]]^a[v[i]])==(s[v[i]]^a[u[i]])) ans++;

	printf("%lld\n",ans);

	return 0;

}

巴特西

「bzoj4264 小C找朋友」

最新文章

热门文章