codeforces 217A ice skating
http://codeforces.com/problemset/problem/217/A 题意:有n个雪漂(那是啥?,从某个雪漂出发走直线,只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂,才能使得可以到达任何一个雪漂。 思路:横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。
一遍AC,有点爽。
/* ***********************************************
Author :111qqz
Created Time :2015年12月05日 星期六 20时18分23秒
File Name :code/problem/217A.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=105;
7int n;
8bool vis[N];
9int x[N],y[N];
vector<int>edge[N];
1void dfs( int x)
2{
3 vis[x] = true;
4 for ( int i = 0 ; i < edge[x].size() ; i++)
5 {
6 int v = edge[x][i];
7 if (!vis[v])
8 {
9 dfs(v);
10 }
11 }
12}
13int main()
14{
15 #ifndef ONLINE_JUDGE
16 freopen("code/in.txt","r",stdin);
17 #endif
scanf("%d",&n);
for ( int i = 0 ; i < n ; i++) scanf("%d %d",&x[i],&y[i]);
1 for ( int i = 0 ; i < n-1 ; i++)
2 {
3 for ( int j = i+1 ; j < n ; j++)
4 {
5 if (x[i]==x[j])
6 {
7 edge[i].push_back(j);
8 edge[j].push_back(i);
9 }
10 if (y[i]==y[j])
11 {
12 edge[i].push_back(j);
13 edge[j].push_back(i);
14 }
1 }
2 }
3 ms(vis,false);
4 int cnt = 0 ;
5 for ( int i = 0 ; i < n ; i++)
6 {
7 if (!vis[i])
8 {
9 dfs(i);
10 cnt++;
11 }
12 }
13 cout<<cnt-1<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}