本文主要是介绍hdu 1198（再续并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*再续并查集 hdu 1198*/
# include<iostream>
# include<cstdio>
# include<cstring>
# include<cstdlib>
# include<cmath>
# include<algorithm>
using namespace std;
const int N=58;
char s[11][5]={"1010","1001","0110","0101",//这里用0或1来代表每块的地的上下左右方向上是否有管口，0就此方向代表无管口，1就代表有管口"1100","0011","1011","1110",//个人觉得这是个好方法，好形象更容易理解，这是在一大神那学的"0111","1101","1111"};
int bin[N][N];
char map[N][N];
int n,m;
int findx(int x)//压缩路径优化操作函数
{if(x!=bin[x/n][x%n])bin[x/n][x%n]=findx(bin[x/n][x%n]);//用递归的思想return bin[x/n][x%n];
}
void merge(int x,int y)//合并集合函数
{int fx,fy;fx=findx(x);fy=findx(y);if(fx!=fy)bin[fy/n][fy%n]=fx;
}
void judge(int i,int j)//判断是否联通函数，分别对map[i][j]上下左右是否联通
{if(j>0&&s[map[i][j]-'A'][2]=='1'&&s[map[i][j-1]-'A'][3]=='1')//用ASCII码的知识，如果两个口都是1 说明都有口那么可以连通merge(i*n+j,i*n+j-1);//所以将这两个合并在一个集合中if(i>0&&s[map[i][j]-'A'][0]=='1'&&s[map[i-1][j]-'A'][1]=='1')//同理merge(i*n+j,(i-1)*n+j);
}
int main()
{while(cin>>m>>n&&(m!=-1||n!=-1)){for(int i=0;i<m;i++){scanf("%s",map[i]);for(int j=0;j<n;j++){bin[i][j]=i*n+j;//对父亲节点进行初始化}}for(int i=0;i<m;i++)for(int j=0;j<n;j++){judge(i,j);}int count=0;for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(bin[i][j]==i*n+j)//判断没有合并的集合，并计算没合并集合的个数，每个集合就是一个连通分支数count++;}cout<<count<<endl;}return 0;
}
/*
总结体会：
这道题有所不同是要我们自己去判断是否联通，那么他的难点也在于此，
如何形象转化去判断是否联通，所以这里用一个个人认为很好的方法
就是用0 1 字符来代表是否有管口。
我相信这种类型转化在以后做题中应该有大的帮助
*/
这篇关于hdu 1198（再续并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
