文章目录

• • 1. 题目来源
  • 2. 题目解析

1. 题目来源

链接：P1536 村村通

2. 题目解析

并查集模板题，维护连通块，连通块个数减一即为需要建设的道路个数。

代码：

// https://www.luogu.com.cn/problem/P1536

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1005;

int n, m;
int fa[N];

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

int main() {
    while (scanf("%d%d", &n, &m), n) {
        for (int i = 1; i <= n; i ++ ) fa[i] = i;
        
        for (int i = 0; i < m; i ++ ) {
            int a, b;
            scanf("%d%d", &a, &b);
            fa[find(a)] = find(b);
        }
        int res = 0;
        for (int i = 1; i <= n; i ++ ) 
            if (fa[i] == i)
                res ++ ;
        printf("%d\n", res - 1);
    }
    return 0;
}