ice skating(冰上滑雪问题)-求解代码疑问
最近看到一个算法问题，是关于冰上滑雪的问题。但是归到实际来说就是在一个整数坐标系中，一直有很多整数点集。就像冰上滑雪一样只能够东南西北移动，在坐标系中即横竖移动。为了保证任意一点到任意一点都能到达，需要建立一些点能够做到，问题就是求出最少点的数量。我看到了一些人的解法，本人初学，对有些地方不太懂，希望各位指教。
代码如下：
long x[102],y[102],i,j,k,n,a;
bool u[102];
void f(long aa)
{
long z;
u[aa]=true;
for(z=0;z<n;z++)
if(!u[z]&&(x[z]==x[aa]||y[z]==y[aa]))
f(z); 这个函数有点疑问，能不能解释得详细点
}
int main()
{
scanf("%ld",&n);
for(i=0;i<n;i++)
scanf("%ld %ld",&x[i],&y[i]);
for(i=0;i<n;i++)
if(!u[i]) 整个if语句解释的清楚点，不是很懂
{
a++;
f(i);
}
printf("%ld\n",a-1);
}
多谢各位了。
[解决办法]
是否只要保证每行每列都有2个雪堆就可以了？
[解决办法]
按横坐标或纵坐标已经相同已经联通的点。来划分成n组。
然后需要额外n-1个点来联通这些组
[解决办法]
可以把f(i)的结果理解为一个集合，这个结合中的所有点之间都是可以到达的,其中点之间可以到达的条件是x[z]==x[aa]
[解决办法]
y[z]==y[aa]，而f(i)就是寻求一个最大的可相互到达的点集合。for(i=0;i<n;i++)if(!u[i]){。。。}这个for循环是用于查找有多少个集合。
另外一个需要理解的是两个集合之间只需要添加一个点就可以连通起来，因为平面线段之间只有相交和平行两种关系。 所以最后的结果为a-1
[解决办法]
建议楼主看一下算法导论里面图的dfs算法。里面每一行都有解释，道理是一样的。
[解决办法]
建议楼主看一下算法导论里的dfs算法
