codeforces 217A ice skating
http://codeforces.com/problemset/problem/217/A 题意：有n个雪漂（那是啥？，从某个雪漂出发走直线，只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂，才能使得可以到达任何一个雪漂。 思路：横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。
一遍AC，有点爽。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月05日 星期六 20时18分23秒
4File Name :code/problem/217A.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35bool vis[N];
36int x[N],y[N];
37
38vector<int>edge[N];
39
40void dfs( int x)
41{
42 vis[x] = true;
43 for ( int i = 0 ; i < edge[x].size() ; i++)
44 {
45 int v = edge[x][i];
46 if (!vis[v])
47 {
48 dfs(v);
49 }
50 }
51}
52int main()
53{
54 #ifndef ONLINE_JUDGE
55 freopen("code/in.txt","r",stdin);
56 #endif
57
58 scanf("%d",&n);
59 for ( int i = 0 ; i < n ; i++) scanf("%d %d",&x[i],&y[i]);
60
61 for ( int i = 0 ; i < n-1 ; i++)
62 {
63 for ( int j = i+1 ; j < n ; j++)
64 {
65 if (x[i]==x[j])
66 {
67 edge[i].push_back(j);
68 edge[j].push_back(i);
69 }
70 if (y[i]==y[j])
71 {
72 edge[i].push_back(j);
73 edge[j].push_back(i);
74 }
75
76 }
77 }
78 ms(vis,false);
79 int cnt = 0 ;
80 for ( int i = 0 ; i < n ; i++)
81 {
82 if (!vis[i])
83 {
84 dfs(i);
85 cnt++;
86 }
87 }
88 cout<<cnt-1<<endl;
89
90 #ifndef ONLINE_JUDGE
91 fclose(stdin);
92 #endif
93 return 0;
94}