历届试题（PREV54）合根植物--查并集应用

港控/mmm° 2022-03-06 23:58 169阅读 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  
样例说明  
　　其合根情况参考下图  
![在这里插入图片描述][20190315185451399.png]  
查并集的相关知识点：[https://blog.csdn.net/niushuai666/article/details/6662911][https_blog.csdn.net_niushuai666_article_details_6662911]

代码如下：（不知道为什么总是超时）

#include<bits/stdc++.h>
    using namespace std;
    int pre[1000]; //查并集数组，用pre表示 
    int ac(int a) 
    {
        int b,temp;
        b=a;
        while(a!=pre[a]) //循环找根结点 
            a=pre[a];
        while(b!=a)//路径压缩
        {
            temp=pre[b];
            pre[b]=a;  //使路径上每个点的上一个点都变为根结点 
            b=temp;
        }
        return a;
    }
    int main()
    {
        int m,n,l;
        cin>>m>>n; 
        int root=m*n; 
        for(int i=0; i<=n*m; i++)
            pre[i]=i;          //初始化 
        cin>>l;
        for(int i=0; i<l; i++)
        {
            int c,d;
            cin>>c>>d;
            int cc=ac(c); 
            int dd=ac(d);
            if(cc!=dd) //合并敌对阵营 
            {
                pre[cc]=pre[dd];
                root--;  
            }
        }
        cout<<root;  //输出剩余阵营数 
    }

[20190315185451399.png]: /images/20220307/ae481a1750614f0aa2b63f80b265649b.png
[https_blog.csdn.net_niushuai666_article_details_6662911]: https://blog.csdn.net/niushuai666/article/details/6662911