目錄

畅通工程-HDU-1232(并查集经典模板)

并查集入门推荐:超有爱的并查集~

题目链接:畅通工程

题意分析:

首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点,让你判断它们是否连通,或者问你整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。像畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
using namespace std;
int pre[1010];

int findd(int root){
    int son,t;
    son=root;
    while(root!=pre[root])
        root=pre[root];
    while(son!=root){
        t=pre[son];
        pre[son]=root;
        son=t;
    }
    return root;
}

int main(){
    int n,m,i,sum,r1,r2,star,end1;
    while(scanf("%d",&n)&&n){
        sum=n-1;
        for(i=1;i<=n;i++)
            pre[i]=i;
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&star,&end1);
            r1=findd(star);
            r2=findd(end1);
            if(r1!=r2){
                pre[r1]=r2;
                sum--;
            }
        }
        printf("%d\n",sum);
    }
	return 0;
}

基础回顾:

find()函数找根结点的两种写法如下:

第一种递归:

1
2
3
4
int find(int x)
{
    return x == pre[x] ? x : find(pre[x]);
}

第二种:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int find(int x)
{
    int root, temp;
    root = x;
    while(root != pre[root])
        root = pre[root];
    while(x != root)
    {
        temp = pre[x];
        pre[temp] = root;
        x = temp;
    }
    return root;
}
合并函数
1
2
3
4
5
6
void join(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        pre[fx]=fy;
}