合根植物题目来源

一开始看到这个题的时候我刚学搜索不就，一想不就是个搜索吗，有什么难的，然后直接就开始搜了，然后就很悲惨的。。超时，超时，超时。。。

再后来就知道了这个

并查集

最好先看一下我的另一篇博客再来看这个会看的更明白一点。

这个题的解题思路和那个什么江湖门派合并（另一篇并查集）差不多，每个植物看成是一个人，每株合并植物看成是一个门派，一开始一株植物是一个门派，各自是各自的掌门，连根现象就是门派合并的过程，最后看有几株植物，就是看还剩几个门派。

话不多说，直接看代码

#include 
     
      using namespace std;int tree[1000010];struct dir{
   int x,y;}a[100001];int m,n,k;int findroot(int root)//找自己的掌门，并且压缩关系，使其只存在一级关系{    int start,t;    start=root;    while(root!=tree[root])        root=tree[root];    while(start!=root)    {        t=tree[start];        tree[start]=root;        start=t;    }    return root;}int main(){    int root1,root2,num;    cin>>m>>n;    num=m*n;    for(int i=1;i<=m*n;i++)        tree[i]=i;    cin>>k;    for(int i=1;i<=k;i++)        cin>>a[i].x>>a[i].y;    for(int i=1;i<=k;i++)    {        root1=findroot(a[i].x);        root2=findroot(a[i].y);        if(root1!=root2)        {            tree[root1]=root2;            num--;        }    }    cout<
     

接下来就放我那个超时（因为超时也不知道运行的结果对不对，反正样例过了就是过了对吧hhh，其实还过了一个点，第二个点就TLE了）的代码吧，做个对比吧。（其实是辛苦写出来的不想删）

#include 
     
      #include
      
       using namespace std;int room[1000][1000];bool code[1000000];bool v[100001];struct dir{
   int x,y;}a[100001];int m,n,k;void bfs(int dx,int dy){    dir start;    queue
       
         q;    start.x=dx;    start.y=dy;    q.push(start);    while(!q.empty())    {        start=q.front();        q.pop();        for(int j=1;j<=k;j++)        {            if(!v[j])            {                if(start.x==a[j].x||start.x==a[j].y||start.y==a[j].x||start.y==a[j].y)                {                    v[j]=true;                    q.push(a[j]);                    code[a[j].x]=true;                    code[a[j].y]=true;                }            }        }    }}int main(){    cin>>m>>n;    int num=1,cnt=0;    for(int i=0;i
        
         >k;    for(int i=1;i<=k;i++)        cin>>a[i].x>>a[i].y;    for(int i=1;i<=k;i++)    {        if(!v[i])        {            v[i]=true;            bfs(a[i].x,a[i].y);            code[a[i].x]=true;            code[a[i].y]=true;            cnt++;        }    }    for(int i=1;i