并查集
include
include
define SIZE 1024
int pre[SIZE];
int Find(int x) { int root = x; while (pre[root] != root){ root = pre[root]; }
int tmp = x;
int next;
while (pre[tmp] != root){
next = pre[tmp];
pre[tmp] = root;
tmp = next;
}
return root;
}
int Join(int x, int y) { int fx = Find(x); int fy = Find(y); if(fx != fy){ pre[fx] = fy; return 1; } else{ return 0; } }
int main() { int a,b; int x,y; int num = 0; scanf("%d %d",&a,&b); num = a;
for(int i=1;i<=a;i++){
pre[i] = i;
}
for(int i=0; i<b;i++){
scanf("%d %d",&x,&y);
int fx = Find(x);
int fy = Find(y);
if (fx != fy){
pre[fx] = fy;
num--;
}
}
printf("%d",num-1);
return 0;
}