POJ-1635, LiveArchive-2935, TJU-1503, ZOJ-1990 : Subway tree systems

問題概要

1.オイラーツアーで、根からの距離の増減の列が与えられるのでグラフを復元する。
2.二つの根付き木が同型であるか判定する。

解法

前者はスタックを用いてO(N)で、後者はハッシュを用いてできる(参考)。

acceptされたコード

計算量O(N*log N)。

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

typedef unsigned long long hash;

const int MAX_L = 3000;
const int MAX_N = MAX_L / 2;

int N;
vector<int> graph[2][MAX_N];
char buf[MAX_L + 1];
int stack[MAX_N], st;
hash shaker[MAX_N];

void build_graph(int k){
	N = 0;
	st = 0;
	stack[st++] = N++;

	for(int i=0; buf[i]; i++){
		if(buf[i] == '0'){
			graph[k][stack[st-1]].push_back(N);
			stack[st++] = N++;
		}
		else{
			st--;
		}
	}
}

void init(){
	for(int k=0; k<2; k++){
		for(int i=0; i<MAX_N; i++){
			graph[k][i].clear();
		}
	}

	for(int k=0; k<2; k++){
		scanf(" %s ", buf);
		const int L = strlen(buf);
		build_graph(k);
	}
}

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

	return ret;
}

bool is_isomorhic(){
	return rec(0, 0) == rec(1, 0);
}

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

	return 0;
}