Advertisement
Guest User

Untitled

a guest
Nov 30th, 2015
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. pair<int,int> points[105];
  6. int id[105],numOfComponents,N;
  7.  
  8. int makeSet(){
  9.     for (int i=0;i<=100;i++){
  10.         id[i]=i;
  11.     }
  12. }
  13.  
  14. int find(int i){
  15.     if (i==id[i])return i;
  16.     return id[i]=find(id[i]);
  17. }
  18.  
  19. void unite(int u,int v){
  20.     int U = find(u);
  21.     int V = find(v);
  22.     if (U!=V){
  23.         id[V]=U;
  24.         numOfComponents--;
  25.     }
  26. }
  27.  
  28. int main(){
  29.     cin >> N;
  30.     makeSet();
  31.     for (int i=0;i<N;i++){
  32.         cin >> points[i].first >> points[i].second;
  33.     }
  34.     numOfComponents=N;
  35.     for (int i=0;i<N;i++){
  36.         for (int j=0;j<N;j++){
  37.             if (i==j)continue;
  38.             if (points[i].first==points[j].first || points[i].second==points[j].second){
  39.                 unite(i,j);
  40.             }
  41.         }
  42.     }
  43.     cout << numOfComponents-1 << endl;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement