This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2821" #include "../../template/template.hpp" #include "../../structure/union-find/union-find.hpp" #include "../../graph/tree/tree-isomorphism.hpp" int main() { int N, M; cin >> N >> M; vector< int > U(M), V(M); UnionFind uf(N); for(int i = 0; i < M; i++) { cin >> U[i] >> V[i]; --U[i], --V[i]; uf.unite(U[i], V[i]); } vector< vector< int > > belong_v(N), belong_e(N); for(int i = 0; i < N; i++) { belong_v[uf.find(i)].emplace_back(i); } for(int i = 0; i < M; i++) { belong_e[uf.find(U[i])].emplace_back(i); } cin >> N; Graph<> t(N); t.read(N - 1); int ret = 0; vector< int > id(belong_v.size()); for(int i = 0; i < (int) belong_v.size(); i++) { if(uf.find(i) == i) { Graph<> g(belong_v[i].size()); int ptr = 0; for(auto &p : belong_v[i]) id[p] = ptr++; for(auto &j : belong_e[i]) { g.add_edge(id[U[j]], id[V[j]]); } ret += tree_isomorphism(t, g); } } cout << ret << endl; }
#line 1 "test/verify/aoj-2821.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2821" #line 1 "template/template.hpp" #include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { explicit FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } #line 4 "test/verify/aoj-2821.test.cpp" #line 2 "structure/union-find/union-find.hpp" struct UnionFind { vector< int > data; UnionFind() = default; explicit UnionFind(size_t sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x), y = find(y); if(x == y) return false; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int k) { if(data[k] < 0) return (k); return data[k] = find(data[k]); } int size(int k) { return -data[find(k)]; } bool same(int x, int y) { return find(x) == find(y); } vector< vector< int > > groups() { int n = (int) data.size(); vector< vector< int > > ret(n); for(int i = 0; i < n; i++) { ret[find(i)].emplace_back(i); } ret.erase(remove_if(begin(ret), end(ret), [&](const vector< int > &v) { return v.empty(); }), end(ret)); return ret; } }; #line 6 "test/verify/aoj-2821.test.cpp" #line 2 "graph/tree/tree-isomorphism.hpp" #line 2 "graph/graph-template.hpp" /** * @brief Graph Template(グラフテンプレート) */ template< typename T = int > struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template< typename T = int > struct Graph { vector< vector< Edge< T > > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector< Edge< T > > &operator[](const int &k) { return g[k]; } inline const vector< Edge< T > > &operator[](const int &k) const { return g[k]; } }; template< typename T = int > using Edges = vector< Edge< T > >; #line 2 "graph/tree/centroid.hpp" #line 4 "graph/tree/centroid.hpp" /** * @brief Centroid(木の重心) * @docs docs/centroid.md */ template< typename T > vector< int > centroid(const Graph< T > &g) { const int N = (int) g.size(); stack< pair< int, int > > st; st.emplace(0, -1); vector< int > sz(N), par(N); while(!st.empty()) { auto p = st.top(); if(sz[p.first] == 0) { sz[p.first] = 1; for(auto &to : g[p.first]) if(to != p.second) st.emplace(to, p.first); } else { for(auto &to : g[p.first]) if(to != p.second) sz[p.first] += sz[to]; par[p.first] = p.second; st.pop(); } } vector< int > ret; int size = N; for(int i = 0; i < N; i++) { int val = N - sz[i]; for(auto &to : g[i]) if(to != par[i]) val = max(val, sz[to]); if(val < size) size = val, ret.clear(); if(val == size) ret.emplace_back(i); } return ret; } #line 5 "graph/tree/tree-isomorphism.hpp" /** * @brief Tree-Isomorphism(木の同型性判定) */ template< typename T > bool tree_isomorphism(const Graph< T > &a, const Graph< T > &b) { if(a.size() != b.size()) return false; const int N = (int) a.size(); using pvi = pair< vector< int >, vector< int > >; auto get_uku = [&](const Graph< T > &t, int e) { stack< pair< int, int > > st; st.emplace(e, -1); vector< int > dep(N, -1), par(N); while(!st.empty()) { auto p = st.top(); if(dep[p.first] == -1) { dep[p.first] = p.second == -1 ? 0 : dep[p.second] + 1; for(auto &to : t[p.first]) if(to != p.second) st.emplace(to, p.first); } else { par[p.first] = p.second; st.pop(); } } return make_pair(dep, par); }; auto solve = [&](const pvi &latte, const pvi &malta) { int d = *max_element(begin(latte.first), end(latte.first)); if(d != *max_element(begin(malta.first), end(malta.first))) return false; vector< vector< int > > latte_d(d + 1), malta_d(d + 1), latte_key(N), malta_key(N); for(int i = 0; i < N; i++) latte_d[latte.first[i]].emplace_back(i); for(int i = 0; i < N; i++) malta_d[malta.first[i]].emplace_back(i); for(int i = d; i >= 0; i--) { map< vector< int >, int > ord; for(auto &idx : latte_d[i]) { sort(begin(latte_key[idx]), end(latte_key[idx])); ord[latte_key[idx]]++; } for(auto &idx : malta_d[i]) { sort(begin(malta_key[idx]), end(malta_key[idx])); if(--ord[malta_key[idx]] < 0) return false; } if(i == 0) return ord.size() == 1; int ptr = 0; for(auto &p : ord) { if(p.second != 0) return false; p.second = ptr++; } for(auto &idx : latte_d[i]) { latte_key[latte.second[idx]].emplace_back(ord[latte_key[idx]]); } for(auto &idx : malta_d[i]) { malta_key[malta.second[idx]].emplace_back(ord[malta_key[idx]]); } } assert(0); }; auto p = centroid(a), q = centroid(b); if(p.size() != q.size()) return false; auto a1 = get_uku(a, p[0]); auto b1 = get_uku(b, q[0]); if(solve(a1, b1)) return true; if(p.size() == 1) return false; auto a2 = get_uku(a, p[1]); return solve(a2, b1); } #line 8 "test/verify/aoj-2821.test.cpp" int main() { int N, M; cin >> N >> M; vector< int > U(M), V(M); UnionFind uf(N); for(int i = 0; i < M; i++) { cin >> U[i] >> V[i]; --U[i], --V[i]; uf.unite(U[i], V[i]); } vector< vector< int > > belong_v(N), belong_e(N); for(int i = 0; i < N; i++) { belong_v[uf.find(i)].emplace_back(i); } for(int i = 0; i < M; i++) { belong_e[uf.find(U[i])].emplace_back(i); } cin >> N; Graph<> t(N); t.read(N - 1); int ret = 0; vector< int > id(belong_v.size()); for(int i = 0; i < (int) belong_v.size(); i++) { if(uf.find(i) == i) { Graph<> g(belong_v[i].size()); int ptr = 0; for(auto &p : belong_v[i]) id[p] = ptr++; for(auto &j : belong_e[i]) { g.add_edge(id[U[j]], id[V[j]]); } ret += tree_isomorphism(t, g); } } cout << ret << endl; }