bzoj4264: 小C找朋友

hash大法好

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define ll long long
#define N 1000006
#define M 2000006

using namespace std;
using std::vector;
inline int read(){
	int ret=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while ('0'<=ch&&ch<='9'){
		ret=ret*10-48+ch;
		ch=getchar();
	}
	return ret;
}

vector<int> e[N];
int n,m;

struct Hash{
	int k,P;
	int hash[N];
	Hash(){}
	void load(){
		memset(hash,0,sizeof(hash));
		for (int i=1;i<=n;++i)
			for (int j=0;j<e[i].size();++j)
				hash[i]=(ll)((ll)hash[i]*k%P+e[i][j])%P;
	}
} h0,h1;

pair<int,int> a[N];

ll ans;
void renew_ans(){
	for (int i=1;i<=n;++i)
		a[i]=make_pair(h0.hash[i],h1.hash[i]);
	sort(a+1,a+n+1);
	int cnt=0;
	for (int i=1;i<=n;++i){
		++cnt;
		if (i==n||a[i]!=a[i+1]){
			ans+=(ll)cnt*(cnt-1)/2;
			cnt=0;
		}
	}
}

int main(){
	h0.k=23;h0.P=2333333;
	h1.k=233;h1.P=1000000007;
	n=read();m=read();
	for (int i=1;i<=m;++i){
		int u=read(),v=read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	ans=0;
	for (int k=0;k<2;++k){
		for (int i=1;i<=n;++i) sort(e[i].begin(),e[i].end());
		h0.load();h1.load();
		renew_ans();
		for (int i=1;i<=n;++i) e[i].push_back(i);
	}
	printf("%lld
",ans);
	return 0;
}