警告
本文最后更新于 2018-07-31，文中内容可能已过时。
3 题意分析
首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。像畅通工程这题，问还需要修几条路，实质就是求有几个连通分支。
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
| #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;
}
|
4 基础回顾
4.1 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;
}
|
4.1.1 合并函数
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;
}
|
Lruihao
支付宝
微信