#include <iostream> using namespace std; #define N 1000 int father[N];//每个元素父亲下标 int height[N]; void Init(int n) { //最开始每一个元素单独构建一个集合 for (int i = 1; i <= n; i++) { father[i] = i;//每个元素都是自己的根 height[i] = 1; } } int find(int x) { if (x != father[x]) { //他还有父亲 //优化,压缩路径,找到祖先后先不返回,而是设置为自己的新父亲 father[x] = find(father[x]); } //x是树的根 return father[x]; } void Union(int x, int y, int &num) { //合并两棵树,也可以路径压缩,大树吞并小树 int X = find(x); int Y = find(y); if (X != Y) { num--; } if (height[X] < height[Y]) { father[X] = Y; } else if (height[X] > height[Y]) { father[Y] = X; } else { father[Y] = X; height[X]++; } } int main() { int n, m; while (scanf("%d %d", &n, &m) != EOF) { if (n == 0 && m == 0) { break; } Init(n); int num = n; for (int i = 0; i < m; i++) { int x, y; scanf("%d%d", &x, &y); Union(x, y, num); } cout << num-1 << endl; } return 0; }