概述
/**
[DFS]cf 134A Ice Skating
给出坐标系中一些点，同一水平或竖直上的两点是可达的。
问至少添加多少点使得任意两点可达。
将联通的点集缩点，任意两个不连通的点集只需添加一个点即可联通
*/
#include <stdio.h>
#define N 128
int x[N],y[N],vis[N];
int n;
void
dfs(int u){
if(vis[u])
return;
vis[u] = 1;
for(int i = 0; i < n; ++i)
if(!vis[i] && (x[i] == x[u] || y[i] == y[u]))
dfs(i);
}
int main(){
int i;
scanf("%d",&n);
for(i = 0; i < n; ++i)
scanf("%d%d",x + i, y + i);
int res = -1;
for(i = 0; i < n; ++i)
if(!vis[i]){
++res;
dfs(i);
}
printf("%dn",res);
return 0;
}最后
以上就是时尚小蚂蚁为你收集整理的[DFS] cf 134A Ice Skating的全部内容，希望文章能够帮你解决[DFS] cf 134A Ice Skating所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[DFS] cf 134A Ice Skating](/uploads/reation/bcimg9.png)
发表评论 取消回复