Advertisement
Saleh127

UVA 10147 / DSU - MST

Nov 5th, 2021
818
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-05-11.30.59
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. vector<ll>parent,rankk;
  12. vector<ll>g[20005];
  13. vector<pair<ll,pair<ll,ll>>>edge;
  14. bool v[20005];
  15. ll cnt;
  16. map<string,ll>x;
  17.  
  18. void make_set(ll n)
  19. {
  20.     for(ll i=0; i<=n+2; i++)
  21.     {
  22.         parent[i] = i;
  23.         rankk[i] = 0;
  24.     }
  25. }
  26.  
  27. ll find_set(ll v)
  28. {
  29.     if (v == parent[v])
  30.     {
  31.         return v;
  32.     }
  33.     return parent[v] = find_set(parent[v]);
  34. }
  35.  
  36. void union_sets(ll a, ll b)
  37. {
  38.     a = find_set(a);
  39.     b = find_set(b);
  40.  
  41.     if (a != b)
  42.     {
  43.         if (rankk[a] < rankk[b])
  44.         {
  45.             swap(a, b);
  46.         }
  47.  
  48.         parent[b] = a;
  49.  
  50.         if (rankk[a] == rankk[b])
  51.         {
  52.             rankk[a]++;
  53.         }
  54.     }
  55. }
  56.  
  57. ll dis(ll x,ll y,ll x1,ll y1)
  58. {
  59.      return (x-x1)*(x-x1)+(y-y1)*(y-y1);
  60. }
  61.  
  62. int main()
  63. {
  64.  
  65.     ll n,m,i,j,k,l;
  66.  
  67.     test
  68.     {
  69.  
  70.         cin>>n;
  71.  
  72.         edge.clear();
  73.         parent.resize(n+5);
  74.         rankk.resize(n+5);
  75.         make_set(n);
  76.  
  77.         vector<pair<ll,ll>>x;
  78.  
  79.         for(i=0;i<n;i++)
  80.         {
  81.             cin>>k>>l;
  82.  
  83.             x.push_back({k,l});
  84.         }
  85.  
  86.  
  87.         cin>>m;
  88.  
  89.         for(i=0;i<m;i++)
  90.         {
  91.              cin>>k>>l;
  92.  
  93.              union_sets(k,l);
  94.         }
  95.  
  96.  
  97.         for(i=0;i<n;i++)
  98.         {
  99.              for(j=i+1;j<n;j++)
  100.              {
  101.                   k=dis(x[i].first,x[i].second,x[j].first,x[j].second);
  102.  
  103.                   edge.push_back({k,{i+1,j+1}});
  104.                   edge.push_back({k,{j+1,i+1}});
  105.              }
  106.         }
  107.  
  108.         sort(edge.begin(),edge.end());
  109.  
  110.         l=0;
  111.  
  112.         for(auto dd:edge)
  113.         {
  114.             if(find_set(dd.second.second)!=find_set(dd.second.first))
  115.             {
  116.                 l=1;
  117.                 union_sets(dd.second.first,dd.second.second);
  118.  
  119.                 cout<<dd.second.first<<" "<<dd.second.second<<nl;
  120.             }
  121.         }
  122.  
  123.  
  124.         if(l==0) cout<<"No new highways need"<<nl;
  125.  
  126.         if(cs<tt) cout<<nl;
  127.  
  128.     }
  129.  
  130.     get_lost_idiot;
  131. }
  132.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement