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; }