SPOJ-TREEISO : Tree Isomorphism

問題概要

ノード数V(<10^5)の木が二つ与えられる。これらが同型であるかどうか判定せよ。

解法

まず根付き木の場合を考える。
頂点vを根とした部分木にハッシュ値f(v)を割り振る。f(v)は子の部分木のハッシュ値の集合から生成するようにする。この際ローリングハッシュ的な生成方法だと何故か頻繁に衝突してしまうことに注意。あとはハッシュ値が一致するかどうか見てやればよい。子のハッシュ値をソートする部分がボトルネックでここで基数ソートしてO(V)と主張することもできなくはないが…。
では無向木の場合はどうするか。
まず木に対して中心を検出する。中心が二つあったときはその間にダミーのノードを置いて中心がユニークになるようにする。あとはそれを根として根付き木の同型判定を行えばよい。

acceptされたコード

計算量O(V*log V)。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long hash;

const int MAX_N = 1e5;

int N, V;
vector<int> graph[2][MAX_N + 1];
int dist[MAX_N], dist2[MAX_N];
bool visited[MAX_N + 1];
hash shaker[MAX_N];

void init(){
	scanf("%d", &N);
	for(int k=0; k<2; k++){
		for(int i=0; i<=N; i++){
			graph[k][i].clear();
		}
	}

	for(int k=0; k<2; k++){
		for(int i=0; i<N-1; i++){
			int x, y;
			scanf("%d%d", &x, &y);
			x--; y--;
			graph[k][x].push_back(y);
			graph[k][y].push_back(x);
		}
	}
}

//flood fill
void dfs(int k, int v){
	visited[v] = true;
	for(int i=0; i<(int)graph[k][v].size(); i++){
		const int u = graph[k][v][i];
		if(!visited[u]){
			dist[u] = dist[v] + 1;
			dfs(k, u);
		}
	}
}

//センターのindexを返す。二つある場合はペアを、一つのときはsecondが-1。
pair<int,int> find_center(int k){
	memset(visited, false, sizeof(visited));
	dist[0] = 0;
	dfs(k, 0);

	int e = max_element(dist, dist + N) - dist;
	memset(visited, false, sizeof(visited));
	memcpy(dist2, dist, sizeof(dist));
	dist[e] = 0;
	dfs(k, e);

	memset(visited, false, sizeof(visited));
	memcpy(dist2, dist, sizeof(dist));
	e = max_element(dist, dist + N) - dist;
	dist[e] = 0;
	dfs(k, e);

	int diameter = *max_element(dist, dist+ N);

	pair<int,int> ret(-1,-1);
	for(int i=0; i<N; i++){
		if( (dist[i] == diameter/2 || dist2[i] == diameter/2) && dist[i] + dist2[i] == diameter){
			if(ret.first == -1){
				ret.first = i;
			}
			else {
				ret.second = i;
			}
		}
	}

	return ret;
}

//vを頂点とする部分木のハッシュ値を計算する。
hash rec(int k, int v){
	hash ret = 1;
	visited[v] = true;
	vector<hash> hs;
	for(int i=0; i<(int)graph[k][v].size(); i++){
		const int u = graph[k][v][i];
		if(!visited[u]){
			hs.push_back(rec(k, u));
		}
	}
	sort(hs.begin(), hs.end());
	for(int i=0; i<(int)hs.size(); i++){
		ret += hs[i] * shaker[i];
	}

	return ret;
}


hash calc_hash(int k){
	pair<int,int> center = find_center(k);
	int root = center.first;

	//センターがふたつある場合ダミーを挿入。
	if(center.second != -1){
		root = N;
		const int v = center.first, u = center.second;

		graph[k][root].push_back(v);
		graph[k][root].push_back(u);

		*find(graph[k][v].begin(), graph[k][v].end(), u) = root;
		*find(graph[k][u].begin(), graph[k][u].end(), v) = root;
	}

	memset(visited, false, sizeof(visited));
	return rec(k, root);
}

//ノードのサイズは同じであることが前提。破壊的。
bool is_isomorhic(){
	return calc_hash(0) == calc_hash(1);
}

int main(){
	for(int i=0; i<MAX_N; i++){
		shaker[i] = rand();
	}
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		puts(is_isomorhic() ? "YES" : "NO");
	}

	return 0;
}