Codeforces 154 C. Double Profiles

問題

n個の頂点、m本の辺からなる無向グラフが与えられる。
このグラフにおいて、頂点のペア(i, j)がdoubleであるとは、
任意のノードkについて、i-kに辺があるときはj-kに辺があり、i-kに辺がないときはj-kに辺がないようなことを言う。
（i-jには辺があってもなくてもいい）

このとき、doubleなペアの総数を求めよ。

制約条件

n, m≦10^6

方針

直接つながっていないi,jについては、
iの隣接ノードとjの隣接ノードが等しければdouble.
これは、頂点ごとに隣接ノードの集合をハッシュで持っておけばO(1)で判定できる。

（ペアを全て試すとTLEなので、等しいハッシュ値を持つ頂点の個数からペアの個数を求める）

直接つながっているノードi,jについては
iの隣接ノードにi自身を加え、jの隣接ノードにj自身を加えてハッシュが等しいかを見る。

ソースコード

int n, m;
vi e[1000001];
ll h[1000001], p[1000001];

void run()
{
	scanf("%d%d",&n,&m);
	p[0]=1;
	rep(i,n)p[i+1]=p[i]*1007;
	rep(i,m){
		int a, b; scanf("%d%d",&a,&b);
		e[--a].pb(--b);
		//e[b].pb(a);
		h[a]+=p[b];
		h[b]+=p[a];
	}
	map<ll,int> cnt;
	rep(i,n)cnt[h[i]]++;
	ll ans=0;
	fr(i,cnt)ans+=(ll)i->second*(i->second-1)/2;
	rep(i,n)rep(j,e[i].size())if(h[i]+p[i]==h[e[i][j]]+p[e[i][j]])ans++;
	cout<<ans<<endl;
}