问题描述
问题分析
体验一把套模板的毫无意义的爽快感
虽然这题很早以前就做过
但这次用了压缩路径加防退化
哎呀……
这套用的我都不知道把题解直接写在并查集说明 还是写到这里了……
就这一题而言……
我勒个去……
没什么说的
标准的并查集
看并查集的说明吧
【看书】并查集——合并与查询
然后输出的是 总集合数-1
便可达到畅通
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
40
41
42
43
44
45
46
| #include<stdio.h>
int par[1020];
int rank[1020];
int find(int m) {
if(par[m]==m) {
return m;
} else
return par[m]=find(par[m]);
}
void unite(int x,int y) {
x=find(x);
y=find(y);
if(x==y)
return;
else {
if(rank[x]<rank[y]) {
par[x]=y;
} else {
par[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}
}
int main() {
int N,M;
while(scanf("%d", &N),N) {
scanf("%d", &M);
for(int i=1; i<=N; i++) {
par[i]=i;
rank[i]=0;
}
while(M--) {
int u,v;
scanf("%d %d",&u,&v);
unite(u,v);
}
int cnt=0;
for(int i=1; i<=N; i++) {
if(par[i]==i)
cnt++;
}
printf("%d\n",cnt-1);
}
return 0;
}
|
题目地址:【杭电】[1232]畅通工程