Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 4141;
  5.  
  6. int n;
  7. vector<int> g[N];
  8. bool cut_point[N];
  9. int color[N], hsh[N], cnt[N];
  10. vector<vector<int>> trees[N];
  11.  
  12. int dfs(int u, int p) {
  13.   int ans = 1;
  14.   vector<int> sz;
  15.   for (int v : g[u]) {
  16.     if (v != p) {
  17.       int z = dfs(v, u);
  18.       ans += z;
  19.       sz.push_back(z);
  20.     }
  21.   }
  22.   sz.push_back(n - ans);
  23.   bool ok = true;
  24.   for (int x : sz)
  25.     ok &= (x == sz[0]);
  26.   cut_point[u] = ok && sz.size() > 1;
  27.   return ans;
  28. }
  29.  
  30. void dfs2(int u, int p, int c) {
  31.   color[u] = c;
  32.   for (int v : g[u])
  33.     if (v != p)
  34.       dfs2(v, u, c);
  35. }
  36.  
  37. void dfs3(int u, int p) {
  38.   int c = color[u];
  39.   hsh[u] = cnt[c];
  40.   ++cnt[c];
  41.   for (int v : g[u]) {
  42.     if (v != p) {
  43.       dfs3(v, u);
  44.       trees[c][hsh[u]].push_back(hsh[v]);
  45.       trees[c][hsh[v]].push_back(hsh[u]);
  46.     }
  47.   }
  48. }
  49.  
  50. bool isomorphic(int t1, int t2) {
  51.   // cek if trees[t1].isomorphling(trees[t2]);
  52. }
  53.  
  54. int main() {
  55.   scanf("%d", &n);
  56.   for (int i = 0; i < n - 1; ++i) {
  57.     int u, v;
  58.     scanf("%d %d", &u, &v);
  59.     --u, --v;
  60.     g[u].push_back(v);
  61.     g[v].push_back(u);
  62.   }
  63.   dfs(0, -1);
  64.   int cnt = 0;
  65.   for (int i = 0; i < n; ++i)
  66.     cnt += cut_point[i];
  67.   if (!cnt)
  68.     return 0 * puts("-1");
  69.   assert(cnt == 1);
  70.   int root;
  71.   for (int i = 0; i < n; ++i)
  72.     if (cut_point[i])
  73.       root = i;
  74.   int p = 0;
  75.   for (int v : g[root]) {
  76.     color[v] = ++p;
  77.     dfs2(v, root, p);
  78.   }
  79.   int sz = 0;
  80.   for (int i = 0; i < n; ++i)
  81.     if (color[i] == 1)
  82.       ++sz;
  83.   for (int i = 1; i <= p; ++i)
  84.     trees[i].resize(sz);
  85.   for (int v : g[root])
  86.     dfs3(v, root);
  87.   // bool ok = true;
  88.   // for (int i = 1; i < p; ++i)
  89.   //   ok &= isomorphic(i, i + 1);
  90.   // printf("%d\n", (ok ? p : -1));
  91.   return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement