Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- pair<int,int> points[105];
- int id[105],numOfComponents,N;
- int makeSet(){
- for (int i=0;i<=100;i++){
- id[i]=i;
- }
- }
- int find(int i){
- if (i==id[i])return i;
- return id[i]=find(id[i]);
- }
- void unite(int u,int v){
- int U = find(u);
- int V = find(v);
- if (U!=V){
- id[V]=U;
- numOfComponents--;
- }
- }
- int main(){
- cin >> N;
- makeSet();
- for (int i=0;i<N;i++){
- cin >> points[i].first >> points[i].second;
- }
- numOfComponents=N;
- for (int i=0;i<N;i++){
- for (int j=0;j<N;j++){
- if (i==j)continue;
- if (points[i].first==points[j].first || points[i].second==points[j].second){
- unite(i,j);
- }
- }
- }
- cout << numOfComponents-1 << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement