HDU 1232 并查集/dfs

原题：

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

我的第一道并查集题目，刚刚学会，我是照着《啊哈算法》这本书学会的，感觉非常通俗易懂，另外还有一篇同样非常好的博客：http://blog.csdn.net/niushuai666/article/details/6662911

这两位大神已经把并查集讲解的非常透彻了，所以我就不班门弄斧了。。。

刚开始看到这道题的时候，我并不知道这里是怎么用到并查集的，可以说我对并查集的理解还不是很到位。看了上面那篇博文后才算有点明白了，并查集的本质就是维护一个森林，适合来解决一个图有几个连通分支的问题。

我刚开始是用深度优先搜索做的，和并查集的本质其实是一样的，就是先存储整个图，然后对每个节点进行深度优先搜索，这个每一次的搜索过程，就是对这个节点所扩展出的独立分支就行遍历，把所到之处的每一个节点进行标记，好下次不再访问已经访问过的节点。最后，我们统计总共进行深搜的次数，这就是对应着有几个独立的分支。当然，这个方法效率并不如并查集高，但也算是为大家提供了另一个思路吧（^_^）

深搜：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define maxn 1005
 4 int map[maxn][maxn],book[maxn];//map用来存储图，book是标记每个点是否已经访问过 
 5 int n,m;
 6 void dfs(int cur){//cur表示当前节点 
 7     for(int i = 1;i<=n;i++){
 8         if(book[i]==0&&map[cur][i]==1){
 9             book[i] = 1;
10             dfs(i);
11         }
12     }
13 }
14 int main(){
15     while(scanf("%d",&n)!=EOF&&n){
16         scanf("%d",&m);
17         memset(map,0,sizeof(map));
18         memset(book,0,sizeof(book));
19         for(int i = 0;i<m;i++){
20             int u,v;
21             scanf("%d%d",&u,&v);
22             map[u][v] = 1;
23             map[v][u] = 1;
24         }
25         int sum = 0;
26         for(int i = 1;i<=n;i++){
27             if(book[i]==0){
28                 book[i] = 1;//这句不要忘了，从当前节点开始搜索时，要标记 
29                 dfs(i);
30                 sum++;
31             }
32         }
33         printf("%d
",sum-1);
34     }
35     return 0;
36 }

View Code

我又用新学到的并查集来写了这道题（代码用了《啊哈算法》里的模板），算是一道非常好的并查集入门题吧~

 1 #include<stdio.h>
 2 #define maxn 1005
 3 int n,m;
 4 int f[maxn];
 5 int getf(int a){
 6     if(f[a]==a){
 7         return a;
 8     }else{
 9         f[a] = getf(f[a]);
10         return f[a];
11     }
12 }
13 //合并函数 
14 void merge(int u,int v){
15     int t1 = getf(u);
16     int t2 = getf(v);
17     if(t1!=t2)
18         f[t2] = t1;
19 }
20 int main(){
21     while(scanf("%d",&n)!=EOF&&n){
22         scanf("%d",&m);
23         //初始化每个节点 
24         for(int i = 1;i<=n;i++)
25             f[i] = i;
26         for(int i = 0;i<m;i++){
27             int u,v;
28             scanf("%d%d",&u,&v);
29             merge(u,v);
30         }
31         int sum = 0;
32         for(int i = 1;i<=n;i++)
33             if(f[i]==i)
34                 sum++;
35         printf("%d
",sum-1);
36     }
37     return 0;
38 }

View Code