CF217A Ice Skating 解题报告

1
2
3
4
2
2 1
1 2

1
2
1

1
2
3
4
2
2 1
4 1

1
2
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// From djq_cpp
// Rating 3180
// reason : 思路清晰，代码简洁明了，运用了vector来储存图，
#include <iostream>
#include <vector>
using namespace std;
int x[100],y[100];
vector <int> nt[100];
bool v[100];
void dfs(int ns)
{
v[ns]=true;
for(int k=0;k<(int)nt[ns].size();k++)
if(!v[nt[ns][k]])dfs(nt[ns][k]);
}
int main()
{
int n,cnt=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
for(int j=0;j<i;j++)
if(x[i]==x[j]||y[i]==y[j])
{
nt[i].push_back(j);
nt[j].push_back(i);
}
}
for(int k=0;k<n;k++)
if(!v[k])
{
dfs(k);
cnt++;
}
cnt--;
cout<<cnt;
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// From xlk
// Rating 2428
// reason : 思路清晰，代码简洁明了，运用了并查集
#include <bits/stdc++.h>
using namespace std;
int n, c;
int x[120];
int y[120];
int f[120];
int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
x = F(x);
y = F(y);
if (x != y)
{
f[x] = y;
c--;
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
f[i] = i;
}
c = n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (x[i] == x[j] || y[i] == y[j])
{
U(i, j);
}
}
}
cout << c - 1 << endl;
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// From Heart_Blue
// Rating 2425
// reason : 思路清晰，代码简洁明了，运用了Class和并查集
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e2 + 10;
int x[N], y[N];
class UnionFind
{
private:
int p[N];
public:
int size(int x)
{
int px = Find(x);
return -p[px];
}
void init()
{
MEM(p, -1);
}
int Find(int x)
{
int root = x;
while (p[root] >= 0) root = p[root];
while (x != root)
{
int tmp = p[x];
p[x] = root;
x = tmp;
}
return root;
}
void Union(int x, int y)
{
int px = Find(x);
int py = Find(y);
if (size(px) > size(py)) swap(px, py);
int total = size(px) + size(py);
p[px] = py;
p[py] = -total;
}
} uf;
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
uf.init();
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
}
int ans = n - 1;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (x[i] != x[j] && y[i] != y[j]) continue;
if (uf.Find(i) != uf.Find(j))
{
uf.Union(i, j);
ans--;
}
}
}
cout << ans << endl;
return 0;
}