http://acm.hdu.edu.cn/showproblem.php?pid=1198水源的数目就是合并后的根的数目，并查集的合并就是对m*n个点的合并，合并有两种方式，水平和垂直。
这道题初始化有点多，通过观察图形，记录图的上下左右四个方位是否连通，然后得出他们彼此之间是否连通。
#include <iostream>
#include <string>
using namespace std;
struct T
{
bool right,left,down,up;
T()
{
right=left=down=up=false;
}
}s[11];
int parent[2502]; //考虑这m*n个点能构成多少个连通分量
bool link1[11][11]; //是否水平相连
bool link2[11][11]; //是否垂直相连
char map[51][51];
void init() //初始化这11张图片是否相连，包括水平、垂直两种方式
{
int i,j;
s[0].left=s[2].left=s[5].left=s[6].left=s[7].left=s[8].left=s[10].left=true;
s[1].right=s[3].right=s[5].right=s[6].right=s[8].right=s[9].right=s[10].right=true;
s[0].up=s[1].up=s[4].up=s[6].up=s[7].up=s[9].up=s[10].up=true;
s[2].down=s[3].down=s[4].down=s[7].down=s[8].down=s[9].down=s[10].down=true;
for(i=0;i<11;i++)
for(j=0;j<11;j++)
{
link1[i][j]=s[i].right && s[j].left;
link2[i][j]=s[i].down && s[j].up;
}
}
int UFfind(int i)
{
int j,temp;
for(j=i;parent[i]>=0;i=parent[i]);
while(j!=i)
{
temp=parent[j];
parent[j]=i;
j=temp;
}
return i;
}
void UFunion(int i,int j)
{
int temp;
i=UFfind(i);
j=UFfind(j);
if(i==j)
return;
temp=parent[i]+parent[j];
if(parent[i]<=parent[j])
{
parent[i]=temp;
parent[j]=i;
}
else
{
parent[j]=temp;
parent[i]=j;
}
}
int main()
{
int i,j,m,n,pi,pj,res;
init();
while(cin>>m>>n,(m+n)!=-2)
{
memset(parent,-1,sizeof(parent));
res=0;
for(i=0;i<m;i++)
cin>>map[i];
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
if(j<n-1 && link1[map[i][j]-'A'][map[i][j+1]-'A'])
{
pi=i*n+j;
pj=i*n+j+1;
UFunion(pi,pj);
}
if(i<m-1 && link2[map[i][j]-'A'][map[i+1][j]-'A'])
{
pi=i*n+j;
pj=(i+1)*n+j;
UFunion(pi,pj);
}
}
for(i=0;i<m;i++) //搜索根的数目
for(j=0;j<n;j++)
if(parent[i*n+j]<0)
res++;
cout<<res<<endl;
}
return 0;
}
posted on 2011-09-15 12:38
大大木马 阅读(305)
评论(0) 编辑 收藏 引用