fork download
copy 
  1. #include <iostream>
  2. #include <cctype>
  3. #include <cstring>
  4. #include <set>
  5. #include <queue>
  6. #include <climits>
  7. #include <vector>
  8. #include <iterator>
  9. #include <algorithm>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <stack>
  13. #include <string>
  14. #include <unordered_map>
  15. #include <map>
  16. #include <list>
  17. #include <iomanip>
  18. #include <ctype.h>
  19. #include <stdio.h>
  20. //****DEFINE****//
  21. #define mod 1000000007
  22. #define pie 3.141592653589793238
  23. #define all(x) x.begin(), x.end()
  24. template <typename A, typename B>
  25. A amax(A &a, B b)
  26. {
  27.     if (b > a)
  28.         a = b;
  29.     return a;
  30. }
  31. template <typename A, typename B>
  32. A amin(A &a, B b)
  33. {
  34.     if (b < a)
  35.         a = b;
  36.     return a;
  37. }
  38. using namespace std;
  39. typedef long long ll;
  40. //****FUNCTIONS****//
  41. bool cmd1(pair<ll, ll> a, pair<ll, ll> b)
  42. {
  43.     if (a.second > b.second)
  44.     {
  45.         return true;
  46.     }
  47.     return false;
  48. }
  49. bool cmd2(int a, int b)
  50. {
  51.     if (a > b)
  52.     {
  53.         return true;
  54.     }
  55.     return false;
  56. }
  57. //**********   TO TAKE INPUT FROM A FILE   ************
  58. //    freopen("input.txt", "r", stdin);
  59. //    freopen("output.txt", "w", stdout);
  60. int dfs(int root, vector<vector<int> > &adj1, vector<int> &vis)
  61. {
  62.     int cnt = 1;
  63.     vis[root] = 1;
  64.     for (auto it : adj1[root])
  65.     {
  66.         if (vis[it] == 0)
  67.         {
  68.             cnt += dfs(it, adj1, vis);
  69.         }
  70.     }
  71.     return cnt;
  72. }
  73. void meena()
  74. {
  75.     int n;
  76.     cin >> n;
  77.     map<string, set<int> > adj;
  78.     map<string, set<int> > adj2;
  79.     for (int i = 0; i < n; i++)
  80.     {
  81.         string x, y;
  82.         cin >> x >> y;
  83.         adj[x].insert(i);
  84.         adj2[y].insert(i);
  85.     }
  86.     vector<vector<int> > adj1(n);
  87.     for (auto it : adj)
  88.     {
  89.         set<int> temp = it.second;
  90.         int prev = -1;
  91.         for (auto it1 : temp)
  92.         {
  93.             if (prev == -1)
  94.             {
  95.                 prev = it1;
  96.             }
  97.             else
  98.             {
  99.                 adj1[it1].push_back(prev);
  100.                 adj1[prev].push_back(it1);
  101.                 prev = it1;
  102.             }
  103.         }
  104.     }
  105.     for (auto it : adj2)
  106.     {
  107.         set<int> temp = it.second;
  108.         int prev = -1;
  109.         for (auto it1 : temp)
  110.         {
  111.             if (prev == -1)
  112.             {
  113.                 prev = it1;
  114.             }
  115.             else
  116.             {
  117.                 adj1[it1].push_back(prev);
  118.                 adj1[prev].push_back(it1);
  119.                 prev = it1;
  120.             }
  121.         }
  122.     }
  123.     vector<int> vis(n, 0);
  124.     int cnt = 0;
  125.     for (int i = 0; i < n; i++)
  126.     {
  127.         if (vis[i] == 0)
  128.         {
  129.             cnt = max(dfs(i, adj1, vis), cnt);
  130.         }
  131.     }
  132.     cout << n - cnt;
  133.     cout << endl;
  134. }
  135. int main()
  136. {
  137.  
  138.     ios_base::sync_with_stdio(false);
  139.     cin.tie(NULL);
  140.     cout.tie(NULL);
  141.  
  142.     int po;
  143.     cin >> po;
  144.     //    po=1;
  145.  
  146.     while (po--)
  147.     {
  148.         meena();
  149.     }
  150. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
1
6
a b
a c
a d
e b
f c
g d
stdout
copy 
0
https://ideone.com/Lvl1xi
language:
C++14 (gcc 8.3)
created:
239 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!