1873: 蓝桥杯2017年第八届真题-合根植物-----C++代码

解题思路:并查集思想：

            1.初始化：每个结点的父亲结点首先设为它本身。

            2.路径压缩（解决特殊情况下的树的层次深而造成的复杂度增大的问题）

            3.合并

注意事项:1.前期未经过路径压缩的树形结构并查集，树的深度有可能是n。

              2.并查集一定要记得初始化。

              3.有些并查集的题目用cin，cout有可能会超时。遇到常数比较大的尽量不要用cin，cout输入输出。

参考代码:

#include

using namespace std;

typedef long long ll;

const int N=1e6+10;

ll p[N],m,n,i,t,a,b;

int find(int x)

{

return x==p[x]?x:(p[x]=find(p[x]));

} 

int main()

{

    cin>>m>>n;

    int root=m*n;  

    for(i=1;i<=root;i++){

        p[i]=i;

    }

    cin>>t;

     for(i=0;i<t;i++){

         cin>>a>>b;

         if(find(a)!=find(b)){

             p[find(a)]=find(b);

             root--;

        }

     }

     cout<<root<<endl;

     return 0;

}