Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
如下:(创建一个集合p++,合并一次则p--)In Reply To:Re:并查集怎么做?我用搜索的 Posted by:hutu_2000 at 2009-04-03 10:11:43 #include <iostream> using namespace std; struct point{ int a,b; }; point root[105][105]; int shifty[4]={-1,0,1,-1}; int shiftx[4]={-1,-1,-1,0}; point index(int x,int y); void unit(point x,point y); int main() { int n,m,i,j,k; char s[105][105]; while(scanf("%d %d",&n,&m)==2&&!(n==0&&m==0)) { int p=0; for(i=0;i<n;i++) scanf("%s",s[i]); for(i=0;i<n;i++) { for(j=0;j<m;j++) { root[i][j].a=i; root[i][j].b=j; } } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(s[i][j]=='@') { for(k=0;k<4;k++) { int x=shiftx[k]+i,y=shifty[k]+j; if(x>=0&&x<n&&y>=0&&y<m) { if(s[x][y]=='@') { if(root[i][j].a==i&&root[i][j].b==j) { point d=index(x,y); //返回x,y的根节点 root[i][j].a=d.a; root[i][j].b=d.b; } else { point d=index(x,y); if(!(root[i][j].a==d.a&&root[i][j].b==d.b)) { unit(root[i][j],d); p--; } } } } } if(root[i][j].a==i&&root[i][j].b==j) p++; } } } printf("%d\n",p); } return 0; } point index(int x,int y) { if(root[x][y].a==x&&root[x][y].b==y) { return root[x][y]; } else { point d=index(root[x][y].a,root[x][y].b); //??? root[x][y].a=d.a; root[x][y].b=d.b; } return root[x][y]; } void unit(point x,point y) { point d=index(y.a,y.b); root[y.a][y.b].a=x.a; root[y.a][y.b].b=x.b; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator