fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define bint __int128
  6. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  7.  
  8. struct HopcroftKarp {
  9.     static const int inf = 1000'000'000;
  10.  
  11.     int n;
  12.     vector<int> l, r, d;
  13.     vector<vector<int>> adj;
  14.  
  15.     HopcroftKarp(int _n, int _m){
  16.         n = _n;
  17.         int p = _n + _m + 1;
  18.         l.assign(p, 0);
  19.         r.assign(p, 0);
  20.         d.assign(p, 0);
  21.         adj.assign(p, {});
  22.     }
  23.  
  24.     void add_edge(int u, int v){
  25.         adj[u].push_back(v + n);
  26.     }
  27.  
  28.     bool bfs() {
  29.         queue<int> q;
  30.         for(int u = 1; u <= n; u++){
  31.             if(not l[u]) d[u] = 0, q.push(u);
  32.             else d[u] = inf;
  33.         }
  34.  
  35.         d[0] = inf;
  36.         while(not q.empty()) {
  37.             int u = q.front();
  38.             q.pop();
  39.             for(auto v : adj[u]){
  40.                 if(d[r[v]] == inf){
  41.                     d[r[v]] = d[u] + 1;
  42.                     q.push(r[v]);
  43.                 }
  44.             }
  45.         }
  46.         return d[0] != inf;
  47.     }
  48.  
  49.     bool dfs(int u) {
  50.         if (not u) return true;
  51.         for (int v : adj[u]) {
  52.             if ( d[ r[v] ] == d[u] + 1 and dfs(r[u]) ) {
  53.                 l[u] = v, r[v] = u;
  54.                 return true;
  55.             }
  56.         }
  57.         d[u] = inf;
  58.         return false;
  59.     }
  60.  
  61.     int maxMatch() {
  62.         int ans = 0;
  63.         while ( bfs() ) {
  64.             for (int u = 1; u <= n; ++u) {
  65.                 if ( not l[u] and dfs(u) ) {
  66.                     ++ans;
  67.                 }
  68.             }
  69.         }
  70.         return ans;
  71.     }
  72. };
  73.  
  74. int n, m;
  75. vector<vector<int>> adj1, adj2;
  76.  
  77. const int N = 101;
  78.  
  79. bool vis[N][N][N][N];
  80. bool dp[N][N][N][N];
  81.  
  82. bool can(int u1, int p1, int u2, int p2){
  83.     if (vis[u1][p1][u2][p2]) return dp[u1][p1][u2][p2];
  84.     vis[u1][p1][u2][p2] = true;
  85.  
  86.     int sz1 = adj1[u1].size() - (p1 > 0), sz2 = adj2[u2].size() - (p2 > 0);
  87.     HopcroftKarp match(sz1, sz2);
  88.  
  89.     int id1 = 0, id2 = 0;
  90.     for(auto v1 : adj1[u1]){
  91.         if(v1 == p1) continue;
  92.         id1++;
  93.         id2 = 0;
  94.         for(auto v2 : adj2[u2]){
  95.             if(v2 == p2) continue;
  96.  
  97.             id2++;
  98.             if(can(v1, u1, v2, u2))
  99.                 match.add_edge(id1, id2);
  100.         }
  101.     }
  102.  
  103.     return dp[u1][p1][u2][p2] = (match.maxMatch() == sz2);
  104. }
  105.  
  106. void getShitDone() {
  107.     cin >> n;
  108.     adj1.resize(n + 1);
  109.     for(int i = 0; i < n - 1; i++){
  110.         int u, v; cin >> u >> v;
  111.         adj1[u].push_back(v);
  112.         adj1[v].push_back(u);
  113.     }
  114.  
  115.     cin >> m;
  116.     adj2.resize(m + 1);
  117.     for(int i = 0; i < m - 1; i++){
  118.         int u, v; cin >> u >> v;
  119.         adj2[u].push_back(v);
  120.         adj2[v].push_back(u);
  121.     }
  122.  
  123.     for(int u = 1; u <= n; u++){
  124.         for(int v = 1; v <= m; v++){
  125.             if(can(u, 0, v, 0)){
  126.                 cout << "Y";
  127.                 return;
  128.             }
  129.         }
  130.     }
  131.  
  132.     cout << "N";
  133. }
  134.  
  135. signed main() {
  136.     _3bkarm
  137.  
  138.     int ts = 1;
  139.     while (ts--) {
  140.         getShitDone();
  141.         if (ts != 0) cout << '\n';
  142.     }
  143.  
  144.     return 0;
  145. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N
https://ideone.com/N1hamH
language:
C++ (gcc 8.3)
created:
7 days 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!