题解 | #畅通工程#

#include "bits/stdc++.h"
using namespace std;
int father[5000];
int height[5000];
struct Edge {
    int begin;
    int end;
    int cost;
    int build;
};

void Inti() {
    for (int i = 0; i < 5000; ++i) {
        father[i] = i;
        height[i] = 1;
    }
}

int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {
    int x_father = Find(x);
    int y_father = Find(y);
    if (height[x_father] > height[y_father]) {
        father[y_father] = x_father;
    } else if (height[x_father] < height[y_father]) {
        father[x_father] = y_father;
    } else {
        father[y_father] = x_father;
        height[x_father]++;
    }
}

bool compare1(Edge x, Edge y) {
    if (x.build != y.build) return x.build > y.build;
    return x.cost < y.cost;
}
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0) {
            break;
        }
        Inti();
        int answer = 0;
        int flag;//1已建
        Edge edge[m];
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &edge[i].begin, &edge[i].end);
            if (Find(edge[i].begin) != Find(edge[i].end)) {
                Union(edge[i].begin, edge[i].end);
            }
        }
//        sort(edge,edge+(n*(n-1))/2,compare1);
        for (int i = 1; i <= n; ++i) {
            if (Find(i) == i) answer++;
        }
        printf("%d\n", answer - 1);
    }
    return 0;
}