【BZOJ4264】小C找朋友

Description

幼儿园里有N个小C，两个小C之间可能是朋友也可能不是。所有小C之间的朋友关系构成了一个无向图，这个无向图中有M条边。

园长ATM发现对于两个（不同的）小Ci和j，如果其他的所有小C要么同时是i,j的朋友，要么同时不是i,j朋友的话，这两个小C就很有可能一起去吃饭，成为一对好*友。出于一些未知的原因，ATM需要你帮他求出可能成为好*友的小C的对数。

Input

第一行一个数N,M，如题目描述。

接下来M行，每行2个数表示一条无向边。

Output

输出可能成为好*友的小C的对数。

Sample Input

3 3
1 2
2 3
1 3

Sample Output

HINT

N,M<=1000000

题解：我们为每一个点赋一个随机权值，然后令s[x]表示所有与x相邻的点的权值的异或和，然后只需要统计出哪些点的s值相同即可。（当然，你也可以采用hash，它们的本质思想是相同的。）

但是你会发现样例很良心的为你指出了一种特殊情况，x和y可以相邻。那么将每个点的s异或上自己的权值再统计一遍就行了，容易发现这两种情况并不会导致重复计算。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=1000010;

int n,m;

ll v[maxn],s[maxn],p[maxn],ans,sum;

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	srand(2333666);

	n=rd(),m=rd();

	int i,a,b;

	for(i=1;i<=n;i++)	v[i]=(ll)rand()*rand()*rand()*rand();

	for(i=1;i<=m;i++)

	{

		a=rd(),b=rd();

		s[a]^=v[b],s[b]^=v[a];

	}

	for(i=1;i<=n;i++)	p[i]=s[i];

	sort(p+1,p+n+1);

	for(sum=0,i=1;i<=n;i++)

	{

		if(p[i]!=p[i-1])	ans+=sum*(sum-1)/2,sum=0;

		sum++;

	}

	ans+=sum*(sum-1)/2;

	for(i=1;i<=n;i++)	p[i]=s[i]^v[i];

	sort(p+1,p+n+1);

	for(sum=0,i=1;i<=n;i++)

	{

		if(p[i]!=p[i-1])	ans+=sum*(sum-1)/2,sum=0;

		sum++;

	}

	ans+=sum*(sum-1)/2;

	printf("%lld",ans);

	return 0;

}

小C

【BZOJ4264】小C找朋友 随机化