根付き木の同型性判定
(tree/ahu.cpp)

• View this file on GitHub
• Last update: 2021-03-25 09:21:12+09:00
• Link: http://wwwmayr.in.tum.de/konferenzen/Jass08/courses/1/smal/Smal_Talk.pdf

できること

与えられた根付き木の決定的なハッシュ値を求める

一般の木について同型性判定を行う場合は、まず木の中心や重心を求め、それらを根にすればよい

計算量

$O(N \log N)$

Verified with

• test/aoj/1613.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif

// http://wwwmayr.in.tum.de/konferenzen/Jass08/courses/1/smal/Smal_Talk.pdf
//BEGIN CUT HERE
struct AHU{
  inline static map<vector<int>, int> I;
  vector< vector<int> > G;
  AHU(int n):G(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  int dfs(int v,int p){
    vector<int> hs;
    for(int u:G[v])
      if(u!=p) hs.emplace_back(dfs(u,v));
    sort(hs.begin(),hs.end());

    int sz=I.size();
    if(!I.count(hs)) I[hs]=sz;
    return I[hs];
  }

  int build(int r=0){
    return dfs(r,-1);
  }
};

//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#line 1 "tree/ahu.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif

// http://wwwmayr.in.tum.de/konferenzen/Jass08/courses/1/smal/Smal_Talk.pdf
//BEGIN CUT HERE
struct AHU{
  inline static map<vector<int>, int> I;
  vector< vector<int> > G;
  AHU(int n):G(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  int dfs(int v,int p){
    vector<int> hs;
    for(int u:G[v])
      if(u!=p) hs.emplace_back(dfs(u,v));
    sort(hs.begin(),hs.end());

    int sz=I.size();
    if(!I.count(hs)) I[hs]=sz;
    return I[hs];
  }

  int build(int r=0){
    return dfs(r,-1);
  }
};

//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Back to top page