Codeforces Round #109 (Div. 1) C : Double Profiles

問題概要

頂点数N(<10^6)、辺数M(<10^6)のシンプルな無向グラフが与えられる。(i,j)を入れ替えてもグラフが同型であるようなペアは何通りあるか求める問題。

解法

ハッシュを使って、各ノードについて隣接する頂点集合を計算しておく。何故かローリングハッシュ風なハッシュ関数使ってる人多かったけど、順序関係ないんだし乱数列のxorや+で計算する方が楽だと思う。しかしハッシュを使っても重いN * log NだとTLEするので注意。mapだとTLEだったのでc++0xでunordered_map使ったら通った。ひどい。

acceptされたコード

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

typedef long long int64;
//typedef unsigned long long hash;
//typedef pair<hash, hash> hp;
typedef unsigned long long hp;

const int MAX_N = (int)(1e6);

vector<int> graph[MAX_N];

int N, M;
hp xors[MAX_N];
hp hs[MAX_N];

/*
hp operator^(const hp& lhs, const hp& rhs){
	return hp(lhs.first ^ rhs.first, lhs.second ^ rhs.second);
}
*/

void init(){
	scanf("%d%d", &N, &M);

	for(int i=0; i<N; i++){
		//hs[i] = hp((hash)rand() * (hash)rand() * (hash)rand() + (hash)rand(), (hash)rand() * (hash)rand() * (hash)rand() + (hash)rand());
		hs[i] = (hp)rand() * (hp)rand() * (hp)rand() + (hp)rand();
	}

	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		xors[x] = xors[x] ^ hs[y];
		xors[y] = xors[y] ^ hs[x];
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
}

int64 solve(){
	int64 ans = 0;

	unordered_map<hp, int> appear;
	for(int i=0; i<N; i++){
		appear[xors[i]]++;
	}

	for(int i=0; i<N; i++){
		ans += appear[xors[i]] - 1;
		for(int j=0; j<(int)graph[i].size(); j++){
			const int x = graph[i][j];
			if(xors[i] == xors[x]){
				ans--;
			}
			else if((xors[i] ^ hs[x]) == (xors[x] ^ hs[i])){
				ans++;
			}
		}
	}

	return ans/2;
}

int main(){
	init();
	cout << solve() << endl;

	return 0;
}