HDU 1232 畅通工程（并查集）

题目链接

中文题，最简单的并查集。午休时间怒 A 一发~

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

int fa[1005];
int n;

int findfa(int x){
    if(fa[x] != x){
        fa[x] = findfa(fa[x]);
    }
    return fa[x];
}

void add(int x, int y){
    if(x > y)
        swap(x, y);
    x = findfa(x);
    y = findfa(y);
    if(x != y){
        fa[y] = x;
        n--;
    }
}

int main(){
    //freopen("a.txt", "r", stdin);
    int m;
    while(scanf("%d", &n) != EOF && n){
        scanf("%d", &m);
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        while(m--){
            int x, y;
            scanf("%d %d", &x, &y);
            add(x, y);
        }
        printf("%dn", --n);
    }
    return 0;
}