HDU 1232 畅通工程(并查集)



#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;

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;
            int x, y;
            scanf("%d %d", &x, &y);
            add(x, y);
        printf("%dn", --n);
    return 0;

Subscribe to Armin's Blog by Email
Armin Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 并查集