洛谷 P1536 村村通（并查集）

嗯...

题目链接：https://www.luogu.org/problemnew/show/P1536

思路：

　　这道题可以看出是并查集的思想，然后用一个while嵌套一下，输入一条路的两个端点，就将这两个端点合并，表示这两个地方可以互相到达。然后从1到n for 一遍，如果这个点的父亲和它本身相同（即它并没有与其他任何的点并在一起），就将数量+1，注意现在的ans是点的个数，要修的路的个数即为点的个数减一。

AC代码：

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

using namespace std;

int f[100005];
int n, m, x, y;

inline int find(int x){
    if(x != f[x])
        f[x] = find(f[x]);
    return f[x];
}//"查 "

int main(){
    while(true){
        int ans = 0;
        scanf("%d", &n);
        if(n == 0)
            return 0;//结束 
        scanf("%d", &m);
        for(int i = 1; i <= n; i++)
            f[i] = i;
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &x, &y);
            int r1 = find(x);
            int r2 = find(y);
            if(r1 != r2){
                f[r1] = r2;
            }//"并"  
        }
        for(int i = 1; i <= n; i++){
            if(find(i) == i){//没与任何点并在一起 
                ans++;//点的个数 
            }
        }
        printf("%d
", ans - 1);//要修的路的条数 
    }
    return 0;
}