畅通工程-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; } |
|---|
腾讯云开发者
