题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=1232

题目大意

多组样例输入，n座城市，m条路，问最少需要修多少条路能使全部城市相互可达。
本质：求图的连通分支数。

解题思路

思路很明确，就是划分块，相互连通的属于同一块，最后数数多少块输出。
难点在于如何存储块？
出来吧！并查集！
大神讲解，绝了！
我就稍微总结一下：
核心代码

int find(int x){//查找x的掌门
    int r=x;//委托 r 去找掌门
    while(r!=fa[r]){//如果r的上级不是r自己（也就是说找到的大侠他不是掌门）
        r=fa[r];// r 就接着找他的上级，直到找到掌门为止
    }
    return r; //找到了掌门
}

void join(int x,int y){//将x，y连在一起（将x，y归于同一门派）
    int rx=find(x),ry=find(y);//找到x，y的掌门
    if(rx!=ry)//掌门不是同一人
        fa[rx]=ry;//让x的掌门当y的掌门的手下
}

优化代码

int find(int x){
    int r=x;
    while(r!=fa[r]){//找根节点
        r=fa[r];
    }
    int i=x,tmp;
    while(i!=r){//路径压缩
        tmp=fa[i];
        fa[i]=r;
        i=tmp;
    }    
    return r;
}

路径压缩（比较难理解，就算理解了也不是很好写）
本质：让x及x的所有上级的父亲全部变成掌门。
代码中，tmp=fa[i];i=tmp; 实现的是i现在指向刚刚i的上级。fa[i]=r; 将i的上级改为掌门。
图片说明

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m;
int pre[N];
int find(int x){
    int r=x;
    while(pre[r]!=r){//找根 
        r=pre[r];
    }

    int i=x,j;
    while(i!=r){//路径压缩 
        j=pre[i];
        pre[i]=r;
        i=j;
    }

    return r;
}
void join(int x,int y){//连接 
    int rx=find(x),ry=find(y);
    if(rx!=ry)
        pre[rx]=ry;
}

void init(){//初始化
    for(int i=1;i<=n;i++)
        pre[i]=i;
}

int main(){
    while(cin>>n>>m&&n){
        init();
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            join(u,v);
        }

        int cnt=-1;
        for(int i=1;i<=n;i++)
            if(pre[i]==i) cnt++;
        cout<<cnt<<endl;
    }
}

代码讲解

注意初始化，将所有点的父亲节点（上级）都置为自己。
输入的同时直接将相连的节点通过join函数连接。
算算有多少掌门，掌门数-1就是连通分支数；而掌门的父节点就是自己，所以找全部节点中父亲节点等于自己的节点就是掌门数。

另一简洁的AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int fa[N];
int n,m;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx!=ry) fa[rx]=ry;
}
void init(){
    for(int i=1;i<=n;i++) fa[i]=i;
}
int main(){
    while(cin>>n&&n){
        init();
        cin>>m;
        while(m--){
            int u,v;
            cin>>u>>v;
            join(u,v);            
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
            if(fa[i]==i) cnt++;
        cout<<cnt-1<<endl;
    }    
}

总结

其实本题不是很难（如果知道用并查集的话，但是我知道用并查集，最后还是不知道怎么算出连通分支数QWQ）
主要是学习并查集，并查集一般用于有关连通区域的题。
最后的最后，我想问上天一句：我什么时候才能成为大佬啊啊啊！！！