Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <map>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <fstream>
- #include <cstdlib>
- using namespace std;
- typedef long long lol;
- int n;
- struct snow
- {
- int pred;
- int x;
- int y;
- };
- snow a[10000];
- bool comp[10000];
- int find_p(int x)
- {
- if (a[x].pred == x)
- return x;
- else
- return a[x].pred = find_p(a[x].pred);
- }
- void union_p(int x, int y)
- {
- int t = rand() % 2;
- if (t == 0)
- swap(x, y);
- a[x].pred = find_p(y);
- return;
- }
- int main()
- {
- scanf("%d", &n);
- for (int i = 0; i<n; i++)
- {
- int x, y;
- scanf("%d%d", &x, &y);
- a[i].pred = i;
- a[i].x = x;
- a[i].y = y;
- }
- for (int i = 0; i<n-1; i++)
- for (int j = i+1; j<n; j++)
- {
- if (a[i].x == a[j].x || a[i].y == a[j].y)
- if (find_p(i) != find_p(j))
- union_p(i,j);
- }
- int k = 0;
- for (int i = 0; i<n; i++)
- if (comp[find_p(i)] == 0)
- {
- k++;
- comp[find_p(i)] = 1;
- }
- printf("%d", k-1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement