洛谷P2307 迷宫-白红宇

洛谷P2307 迷宫

阅读量：6543 次

发布时间：2019-06-24

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

~~怎么又是一道叫迷宫的题呀QWQ~~

这道题主要是对并查集的考察，需要注意的坑点在于有可能存在的不止一个联通块。

我们只需要对输入的两个数据进行判断，如果在一个集合中证明有多条路则输出0，如果不在一个集合中就合并到同一个集合中。

这道题的输入或许大概可能也会是坑？！qwq

AC代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 100100using namespace std;bool sign;bool book;int f[MAXN+10];int done[MAXN+10];int find(int u){    if(f[u]==u) return u;    else return f[u]=find(f[u]);}int main(){    while(1)    {        book=0;        memset(done,0,sizeof(done));        for(int i=1;i<=MAXN;i++)        {            f[i]=i;        }        while(1)        {            int x,y;            scanf("%d%d",&x,&y);//            printf("x=%d y=%d\n",x,y);            if(x==0)            {                break;            }            if(x==-1)            {                book=1;                sign=1;                break;            }            done[x]=1;            done[y]=1;            int a=find(x);//            printf("a=%d\n",a);            int b=find(y);//            printf("b=%d\n",b);            if(a==b&&!book)            {                 book=1;//              printf("book=%d",book);                printf("0\n");            }            else            {                f[a]=b;            }        }        if(sign) break;        int total=0;        for(int i=1;i<=MAXN;i++)        {            if(f[i]==i&&done[i])            {                total++;            }        }        if(!book&&total==1) printf("1\n");        if(!book&&total!=1) printf("0\n");    }    return 0;}

一开始yy了一个假算法骗了40分

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define INF 0x3f3f3f3f#define MAXN 200000using namespace std;vector
           
             G[MAXN];int num[MAXN];bool sign;int cur[MAXN];bool vis;queue
            
              q;int main(){ while(1) { int mx=0; memset(num,0,sizeof(num)); memset(G,0,sizeof(G)); memset(cur,0,sizeof(cur)); while(1) { int x,y; scanf("%d%d",&x,&y); if(x==0) break; if(x==-1) { sign=1; break; } mx=max(mx,x); mx=max(mx,y); num[x]++; num[y]++; G[x].push_back(y); G[y].push_back(x); } if(sign) break; for(int i=1;i<=mx;i++) { vis=0; if(num[i]!=0) { q.push(i); while(!q.empty()) { int r=q.front(); q.pop(); for(int j=0;j
             
              1) { printf("0\n"); vis=1; break; } q.push(p); } } if(vis) break; } if(vis) break; } } if(!vis) printf("1\n"); } return 0;}