codeforces 217A ice skating

2015-12-05 · 1 min read · dfs tree

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}