[蓝桥杯][2017年第八届真题]合根植物(并查集)-白红宇

[蓝桥杯][2017年第八届真题]合根植物(并查集)

阅读量：5323 次

发布时间：2019-06-14

本文共 1094 字，大约阅读时间需要 3 分钟。

w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。

接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)

接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5 * 4 的小格子，编号：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

17 18 19 20

样例输入

5 4162 31 55 94 87 89 1010 1111 1210 1412 1614 1817 1815 1919 209 1313 17

样例输出

5 代码：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 const int maxn=1e6+5;typedef long long ll;using namespace std;int pre[maxn];int find(int x){ if(x==pre[x]) { return x; } else { return pre[x]=find(pre[x]); }}void Merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) { pre[fx]=fy; } return;}int main(){ int n,m; cin>>n>>m; int k; cin>>k; for(int t=1;t<=n*m;t++) { pre[t]=t; } int x,y; for(int t=0;t