C语言并查集例子——图问题巧用parent[]数组
标签：style 编号 输入 ++ eof == 正整数 pre efi
输入：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( 注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
输出：对每个测试用例，在1行里输出最少还需要建设的道路数目。
#include
#include #define CITYNUMBER 1000
int find_root(int x,int parent[]){
int x_root=x;
while(parent[x_root]!=-1){
x_root=parent[x_root];
}
return x_root;
}
int union_vertices(int x,int y,int parent[],int rank[]){
int x_root=find_root(x,parent);
int y_root=find_root(y,parent);
if(x_root==y_root){
return 0;
}else{
//parent[x_root]=y_root;
if(rank[x_root]>rank[y_root]){
parent[y_root]=x_root;
}else if(rank[y_root]>rank[x_root]){
parent[x_root]=y_root;
}else{
parent[x_root]=y_root;
rank[x_root]++;
}
return 1;
}
}
void initialized(int parent[],int rank[]){
for(int i=0;i){
parent[i]=-1;
rank[i]=-1;
}
}
int main()
{
int n,m,array[CITYNUMBER][2];
int parent[CITYNUMBER]={0};
int rank[CITYNUMBER]={0};
while(scanf("%d",&n)!=EOF&&n!=0){
initialized(parent,rank);
scanf("%d",&m);
for(int i=0;i){
scanf("%d%d",&array[i][0],&array[i][1]);
parent[array[i][0]]=array[i][1];
}
int roadNumAdd=0;
for(int i=1;i){
for(int j=1;j){
int retu=union_vertices(i,j,parent,rank);
if(retu==1){
roadNumAdd++;
}
}
}
printf("还需路条数：%d",roadNumAdd);
}
return 0;
}
C语言并查集例子——图问题巧用parent[]数组
标签：style 编号 输入 ++ eof == 正整数 pre efi
原文地址：https://www.cnblogs.com/lyxcode/p/11134598.html
评论