Advertisement
a53

unghidrept

a53
Feb 11th, 2021 (edited)
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. namespace FastRead
  3. {
  4. const int Dim(1e5);
  5. char buff[Dim];
  6. int pos,len;
  7. inline char nc()
  8. {
  9. if (pos==len)
  10. {
  11. pos=0;
  12. len=fread(buff,1,Dim,stdin);
  13. if(!len)
  14. return EOF;
  15. }
  16. return buff[pos++];
  17. }
  18.  
  19. template<class T> inline void Read(T& x) {
  20. char ch;
  21. int sgn(1);
  22. while(!isdigit(ch=nc()))
  23. if(ch=='-')
  24. sgn=-1;
  25. x=ch-'0';
  26. while(isdigit(ch=nc()))
  27. x=x*10+(ch-'0');
  28. x*=sgn;
  29. }
  30. }
  31.  
  32. using namespace FastRead;
  33. using namespace std;
  34. vector<int> f,cx,cy,freqx,freqy;
  35. unordered_map<int,int> hx,hy;
  36. vector<pair<int,int>> v;
  37. int n,ix,iy,x,y;
  38. long long res;
  39.  
  40. inline int Find(const int& x)
  41. {
  42. return (x==f[x])?x:(f[x]=Find(f[x]));
  43. }
  44.  
  45. int32_t main()
  46. {
  47. Read(n);
  48. v.resize(n);
  49. for(pair<int, int>&P:v)
  50. {
  51. Read(P.first),Read(P.second);
  52. cx.emplace_back(P.first);
  53. cy.emplace_back(P.second);
  54. }
  55. sort(cx.begin(),cx.end());
  56. cx.erase(unique(cx.begin(),cx.end()),cx.end());
  57. for(const int& x:cx)
  58. hx[x]=++ix;
  59. sort(cy.begin(),cy.end());
  60. cy.erase(unique(cy.begin(),cy.end()),cy.end());
  61. for(const int& y:cy)
  62. hy[y]=++iy;
  63. f=freqx =freqy=vector<int>(ix+iy+1);
  64. for(int i=1;i<=ix+iy;++i)
  65. f[i]=i;
  66. for(const pair<int,int>& P:v)
  67. {
  68. x=hx[P.first];
  69. y=hy[P.second]+ix;
  70. f[Find(x)]=Find(y);
  71. }
  72. for(int i=1;i<=ix;++i)
  73. ++freqx[Find(i)];
  74. for(int i=ix+1;i<=ix+iy;++i)
  75. ++freqy[Find(i)];
  76. res=-n;
  77. for(int i=1;i<=ix+iy;++i)
  78. res+=1LL*freqx[i]*freqy[i];
  79. cout<<res;
  80. return 0;
  81. }
  82.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement