## hdu1232畅通工程 并查集 转

YYQ_ZJL

``````#include<iostream>
#define maxn 1005
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
int set[maxn];
int ifhas[maxn];
int s,e;
int n,m;
void init()
{
int i,j;
for(i = 1;i <= n;i ++){
set[i] = i;
ifhas[i] = 0;
}
}
void Merge(int a,int b)
{
int big,small;
big = max(set[a],set[b]);
small= min(set[a],set[b]);
for(int i = 1;i <= n;i ++)
{
if(set[i] == big){
set[i] = small;
}
}
}
int main(void)
{
while(cin >> n && n!=0)
{
init();
cin >> m;
int i,j;
for(i = 0;i < m;i ++){
cin >> s >> e;
Merge(s,e);
}
int ans = 0;
for(int i = 1;i <= n;i ++)
{
if(ifhas[set[i]] == 0){
ans ++;
ifhas[set[i]] = 1;
}
}
cout << ans - 1 << endl;
}
return 0;
}``````

树结构code2

``````#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];void init(int n)
{
int i;
for(i = 1;i <=n;i ++)
{
set[i] = i;
}
}
int find(int x)
{
int fa = x;
while(fa != set[fa])
fa = set[fa];
return fa;
}
void merge(int a,int b)
{
int fa,fb;
fa = find(a);
fb = find(b);
set[fb] = fa;
}
int main()
{
int n,m,a,b;

while(cin >> n && n!= 0)
{
init(n);
cin >> m;
for(int i = 1;i <= m;i ++){
cin >> a >> b;
merge(a,b);
}
for(int i = 1;i <= n;i ++){
set[i] = find(i);
//cout << "set[" << i << "]=" << set[i] << endl;
}
int ans = 0;
for(int i = 1;i <= n;i ++)
{
if(set[i] == i){
ans ++;
}
}
cout << ans - 1 << endl;
}
return 0;
}``````

``````#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];
int height[maxn];
void init(int n)
{
int i;
for(i = 1;i <=n;i ++)
{
set[i] = i;
height[i] = 1;
}
}
int find(int x)
{
int fa = x;
while(fa != set[fa])
fa = set[fa];
return fa;
}
void merge(int a,int b)
{
int fa,fb;
fa = find(a);
fb = find(b);
if(height[fa] > height[fb]){
set[fb] = fa;
}
else if(height[fb] > height[fa]){
set[fa] = fb;
}
else{
set[fb] = fa;
height[fa] ++;
}
}
int main()
{
int n,m,a,b;

while(cin >> n && n!= 0)
{
init(n);
cin >> m;
for(int i = 1;i <= m;i ++){
cin >> a >> b;
merge(a,b);
}
for(int i = 1;i <= n;i ++){
set[i] = find(i);
//cout << "set[" << i << "]=" << set[i] << endl;
}
int ans = 0;
for(int i = 1;i <= n;i ++)
{
if(set[i] == i){
ans ++;
}
}
cout << ans - 1 << endl;
}
return 0;
}``````

``````#include <iostream>
#include <algorithm>
#define maxn 1005
using namespace std;
int set[maxn];
int height[maxn];
void init(int n)
{
int i;
for(i = 1;i <=n;i ++)
{
set[i] = i;
height[i] = 1;
}
}
int find(int x)
{
int fa = x;
int j,i;
while(fa != set[fa])
fa = set[fa];
i = x;
while(i != fa)
{
j = set[i];
set[j] = fa;
i = j;
}
return fa;
}
void merge(int a,int b)
{
int fa,fb;
fa = find(a);
fb = find(b);
if(height[fa] > height[fb]){
set[fb] = fa;
}
else if(height[fb] > height[fa]){
set[fa] = fb;
}
else{
set[fb] = fa;
height[fa] ++;
}
}
int main()
{
int n,m,a,b;

while(cin >> n && n!= 0)
{
init(n);
cin >> m;
for(int i = 1;i <= m;i ++){
cin >> a >> b;
merge(a,b);
}
for(int i = 1;i <= n;i ++){
set[i] = find(i);
//cout << "set[" << i << "]=" << set[i] << endl;
}
int ans = 0;
for(int i = 1;i <= n;i ++)
{
if(set[i] == i){
ans ++;
}
}
cout << ans - 1 << endl;
}
return 0;
}``````

### YYQ_ZJL

08/03
0
0
hdu-1979-继续畅通工程

Big_laoshu
2017/11/20
0
0

dingyihui2016的博客
2017/12/21
0
0
【畅通工程 HDU - 1232 】【并查集模板题】

AJudge
08/22
0
0
【还是畅通工程 HDU - 1233】【Kruskal模板题】

Kruskal算法讲解 该部分内容全部摘录自刘汝佳的《算法竞赛入门经典》 Kruskal算法的第一步是给所有边按照从小到大的顺序排列。 这一步可以直接使用库函数 qsort或者sort。 接下来从小到大依次...

AJudge
08/22
0
0

Java读取Excel 2007

22分钟前
3
0

chenhongjiang
27分钟前
3
0
Makefile中.PHONY的作用是什么？

.PHONY在Makefile中是什么意思？ 我已经经历过了 ，但是它太复杂了。 有人可以简单地向我解释吗？ #1楼 .PHONY: install 表示“安装”一词在此Makefile中不代表文件名； 表示Makefile与同一...

28分钟前
2
0
vmware 共享文件夹不显示文件的问题

34分钟前
3
0
mysql对子查询的优化改写

《高性能mysql第三版》提到mysql会将in子查询改写成exists查询（书中基于的mysql版本是5.1.50和5.5） 但是在5.6之后，已经优化成使用半连接查询 SELECT class_num, class_name FROM class WH...

os_m
36分钟前
3
0