# 畅通工程-HDU-1232（并查集经典模板）

## 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 #include 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; }``````

Buy me a coffee~