fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef vector< vector<int> > Graph;
  4. typedef long long int ll;
  5.  
  6. Graph ginput(int n, int m) {
  7.     Graph G(n);
  8.     for(int i=0; i<m; i++) {
  9.         int s, t; cin >> s >> t;
  10.         s--; t--;
  11.         G[s].push_back(t);
  12.         G[t].push_back(s);
  13.     }
  14.     return G;
  15. }
  16.  
  17. vector<Graph> Forest2Trees(Graph &G) {
  18.     int n = (int)G.size();
  19.     vector<int> vtxid(n, -1);
  20.  
  21.     vector<Graph> ret;
  22.     for(int i=0; i<n; i++) {
  23.         if(vtxid[i] >= 0) continue;
  24.         Graph Tree(1);
  25.         int cur = 0;
  26.         vtxid[i] = cur++;
  27.  
  28.         queue<int> q; q.push(i);
  29.         while(!q.empty()) {
  30.             int k = q.front(); q.pop();
  31.             for(size_t x=0; x<G[k].size(); x++) {
  32.                 int to = G[k][x];
  33.                 if(vtxid[to] >= 0) continue;
  34.                 vtxid[to] = cur++;
  35.                 Tree.push_back(vector<int>());
  36.                 Tree[ vtxid[k ] ].push_back( vtxid[to] );
  37.                 Tree[ vtxid[to] ].push_back( vtxid[k ] );
  38.                 q.push(to);
  39.             }
  40.         }
  41.         ret.push_back(Tree);
  42.     }
  43.     return ret;
  44. }
  45.  
  46. void dfs(int p, Graph &G, vector<int> &dist) {
  47.     if(dist[p] == -1) dist[p] = 0;
  48.     int cur = dist[p];
  49.     for(size_t i=0; i<G[p].size(); i++) {
  50.         int to = G[p][i];
  51.         if(dist[to] != -1) continue;
  52.         dist[to] = cur + 1;
  53.         dfs(to, G, dist);
  54.     }
  55. }
  56.  
  57. vector<int> getCenters(Graph &G) {
  58.     int n = (int)G.size();
  59.     vector<int> d0(n, -1), d1(n, -1), d2(n, -1);
  60.     dfs(0, G, d0);
  61.     int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
  62.     dfs(p1, G, d1);
  63.     int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
  64.     dfs(p2, G, d2);
  65.  
  66.     vector<int> ret;
  67.     int diameter = d2[p1];
  68.     for(int i=0; i<n; i++) {
  69.         bool b1 = (d1[i] + d2[i] == diameter);
  70.         bool b2 = (d1[i] == diameter / 2 || d2[i] == diameter / 2);
  71.         if(b1 && b2) ret.push_back(i);
  72.     }
  73.     return ret;
  74. }
  75.  
  76. map<string, ll> HASHMAP;
  77. ll cntPattern, TreeHash;
  78.  
  79. ll getHash(Graph &G, int point, int parent = -1) {
  80.     // leaf
  81.     if(G[point].size() == 1 && parent != -1)
  82.         return HASHMAP["0"] = 1;
  83.  
  84.     vector<string> rec;
  85.     for(size_t i=0; i<G[point].size(); i++) {
  86.         int to = G[point][i];
  87.         if(to == parent) continue;
  88.         ll temp = getHash(G, to, point);
  89.         rec.push_back(to_string(temp));
  90.     }
  91.     sort(rec.begin(), rec.end());
  92.     string pat = "";
  93.     for(size_t i=0; i<rec.size(); i++) pat += rec[i];
  94.     if(!HASHMAP.count(pat)) HASHMAP[pat] = ++cntPattern;
  95.     return HASHMAP[pat];
  96. }
  97.  
  98. int main() {
  99.     cntPattern = 1;
  100.     int s1, s2;
  101.     int n1, m1; cin >> n1 >> m1;
  102.     Graph Forest = ginput(n1, m1);
  103.     vector<Graph> Trees = Forest2Trees(Forest);
  104.  
  105.     int n2; cin >> n2;
  106.     Graph Pattern = ginput(n2, n2-1);
  107.     vector<int> patCenters = getCenters(Pattern);
  108.     s1 = (int)patCenters.size();
  109.     vector<ll> patHashes;
  110.     for(int i=0; i<s1; i++)
  111.         patHashes.push_back( getHash(Pattern, patCenters[i]) );
  112.  
  113.     int ans = 0;
  114.     for(size_t i=0; i<Trees.size(); i++) {
  115.         if(Trees[i].size() != Pattern.size()) continue;
  116.         vector<int> treeCenters = getCenters(Trees[i]);
  117.         s2 = (int)treeCenters.size();
  118.         if(s1 != s2) continue;
  119.         for(int j=0; j<s2; j++) {
  120.             ll treeHash = getHash(Trees[i], treeCenters[j]);
  121.             if(treeHash == patHashes[0]) {
  122.                 ans++; break;
  123.             }
  124.         }
  125.     }
  126.     cout << ans << endl;
  127.     return 0;
  128. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
6 4
1 2
2 3
2 4
5 6
4
2 3
3 1
3 4
stdout
copy 
1
https://ideone.com/upgMrP
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!