|
#include <iostream>
#include <algorithm>
#include<stdio.h>
#include<math.h>?
using namespace std;
struct point
{
?? ?int root;
}c[1001];
int main()
{
?? ?int N,M,i,s,e,r;
?? ?while(scanf("%d",&N)!=EOF,N)//如果出现某个变量值不对，可能是scanf中%打成了&?
?? ?{
?? ??? ?scanf("%d",&M);
?? ??? ?for(i=1;i<=N;i++)
?? ??? ?{
?? ??? ??? ?c[i].root=i;//初始化城镇的根?
?? ??? ?}
?? ??? ?
?? ??? ?while(M--)//一个语句错了最好检查所有语句，因为我喜欢复制粘贴,?
?? ??? ?{
?? ??? ??? ?scanf("%d %d",&s,&e);//使用逗号这样写虽然简便，但要注意会先执行一次scanf，然后再判断M是否为0?
?? ??? ??? ?while(e!=c[e].root)
?? ??? ??? ?{
?? ??? ??? ??? ?e=c[e].root;//找到根节点?
?? ??? ??? ?}
?? ??? ??? ?while(s!=c[s].root)
?? ??? ??? ?{
?? ??? ??? ??? ?s=c[s].root;//找到根节点?
?? ??? ??? ?}
?? ??? ??? ?c[e].root=s;//注意并查集是集合为概念合并，以树的方式实现,注意当一个城镇出现多次对根赋值，如何保证根的唯一性?
?? ??? ?}//合并集合,应该把注意力集中到根节点上面，只要两个根节点并到一个集合内，两个集合就合并了?
?? ??? ?r=-1;//初始化r,前面当临时变量用了一下
?? ??? ?for(i=1;i<=N;i++)
?? ??? ?{
?? ??? ??? ?if(c[i].root==i)r++;
?? ??? ?}
?? ??? ?printf("%d\n",r);
?? ?}
?? ?
?? ?return 0;
}
总结
1.如同while(scanf("%d",&n),n--)，会先执行一次scanf，再判断n是否为零，相比while(n--)scanf("%d",&n)；要多执行一次scanf
|