HDU 1198（并查集）

时间：2021-10-30 15:14:58

题意：给你11个图，每一个都有管道，然后给一张由这11个正方形中的n个组成的图，判断有几条连通的管道；

思路：在大一暑假的时候做过这道题，当时是当暴力来做的，正解是并查集，需要进行一下转换；

转换1：将子图中的管道转换为数字码，通为1，不通为0；

转换2：一维--->二维，i,j换成在n*m中的第几个，p[i][j] = i*n+j,而且find_set，Union也需要独一无二的坐标来进行判断，然后转换成2维去具体比较；

 #include<stdio.h>

 char a[][]= {"","","","","","","","","","",""};

 int p[][];

 char G[][];

 int n,m;

 int find_set(int x)///查找父节点，并压缩路径

 {

     int r = x/n;

     int c = x % n;

     if(p[r][c]!=x)

         p[r][c]=find_set(p[r][c]);

     return p[r][c];

 }

 void Union(int x,int y)///合并x,y的集合

 {

     x=find_set(x);

     y=find_set(y);

     if(x!=y)

         p[y/n][y%n]=x;

 }

 int main()

 {

     int i,j,sum;

     while(scanf("%d%d",&m,&n)!=-&&(n!=-||m!=-))

     {

         for(i=; i<m; i++)

         {

             scanf("%s",G[i]);

             for(j=; j<n; j++)

                 p[i][j]=i*n+j;///将父节点初始化

         }

         for(i=; i<m; i++)

             for(j=; j<n; j++)

             {

                 ///判断两个方向就好了

                 if(j>&&a[G[i][j]-'A'][]==''&&a[G[i][j-]-'A'][]=='')

                     Union(i*n+j,i*n+j-);

                 if(i>&&a[G[i][j]-'A'][]==''&&a[G[i-][j]-'A'][]=='')

                     Union(i*n+j,(i-)*n+j);

             }

         sum=;

         for(i=; i<m; i++)

             for(j=; j<n; j++)

                 if(p[i][j]==i*n+j)

                     sum++;

         printf("%d/n",sum);

     }

     return ;

 }

相关文章