题解 | #畅通工程#

#include <iostream>
using namespace std;

const int MAXN = 1000 + 10;
int father[MAXN];
int height[MAXN];

void Initial(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}
int Find(int n) {
    if (n != father[n]) {
        father[n] = Find(father[n]);
    }
    return father[n];
}
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a!= b) {
        if (height[a] < height[b]) {
            father[a] = b;
        } else if (height[a] > height[b]) {
            father[b] = a;
        } else {
            father[b] = a;
            height[a]++;
        }
    }
    return;
}
int main() {
    int n, m;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        cin >> m;
        Initial(n);
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            Union(a, b);
        }
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            if (Find(i) != Find(i - 1)) {
                Union(i, i - 1);
                ans++;
            }
        }
        cout << ans << endl;

    }

}
// 64 位输出请用 printf("%lld")