算法设计——并查集

拼搏现实的明天。 2023-10-05 17:32 22阅读 0赞

## 【蓝桥杯】 历届试题 合根植物 ##

问题描述  
　　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 4  
16  
2 3  
1 5  
5 9  
4 8  
7 8  
9 10  
10 11  
11 12  
10 14  
12 16  
14 18  
17 18  
15 19  
19 20  
9 13  
13 17  
样例输出  
5

样例说明  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz_size_5_color_FFFFFF_t_70]  
  
  
源代码

#include<iostream>
    using namespace std;
    const int MAX = 10001;
    int m, n;
    int pre[MAX];
    
    void init(int N) {
        
        for (int i = 1; i <= N; i++)
            pre[i] = i;
    }
    int find(int key) {
        
        if (pre[key] == key)
            return key;
        return pre[key] = find(pre[key]);
        //while(pre[key]!=key)
            //i=pre[i];
        //return i;
    }
    
    void join(int x, int y)
    {
        
        int rx = find(x);
        int ry = find(y);
        if (rx != ry)
            pre[rx] = ry;
    }
    int main() {
        
    
        int x, y, line;
        cin >> m >> n >> line;
        init(m * n);
        for (int i = 0; i < line; i++)
        {
        
            cin >> x >> y;
            join(x, y);
        }
        int ans = 0;
        for (int i = 1; i <= m * n; i++) {
        
    
            if (pre[i] == i)
                ans++;
        }
        cout << ans;
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz_size_5_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210110222458814.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ExMzY4MDg5MzIz,size_5,color_FFFFFF,t_70