题解 P2307 【迷宫】

vegetabird · 2017-08-02 15:10:31 · 题解

大神们都用并查集，蒟蒻只能跑搜索了。。。

不过判断是否连通，是否有环似乎搜索也够了

对于搜到的每一个点，遍历与其相邻的每一个点，如果该点不是当前点的父节点且已经被搜过，则这个图不是树

如果该点未被搜索过，则继续搜下去

搜索后看一看是不是所有点都被搜到了

如果没有，则不是树

CODE:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
int n,m;
int a[500010],b[500010],fst[100010],nxt[500010];
bool vis[100010];
bool exist[100010];
int num[100010];
int q[100010],head,tail;
int x,y;
bool avai;
void dfs(int u,int pre){
    vis[u]=true;
    for(int k=fst[u];k;k=nxt[k]){
        if(b[k]==pre)continue;
        if(vis[b[k]]){
            avai=false;
            return;
        }
        dfs(b[k],u);
    }
}
int main(){
    int i,j,k;
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        if(x<0&&y<0)return 0;
        n=m=0;
        while(x>0&&y>0){
            m++;
            a[m*2-1]=x,b[m*2-1]=y;
            a[m*2]=y,b[m*2]=x;
            if(!exist[x]){
                num[++n]=x;
                fst[x]=0;
                vis[x]=false;
                exist[x]=true;
            }
            if(!exist[y]){
                num[++n]=y;
                fst[y]=0;
                vis[y]=false;
                exist[y]=true;
            }
            nxt[m*2-1]=fst[x];
            fst[x]=m*2-1;
            nxt[m*2]=fst[y];
            fst[y]=m*2;
            scanf("%d%d",&x,&y);
        }
        avai=true;
        dfs(num[1],0);
        for(i=1;i<=n;i++){
            if(!vis[num[i]]){
                avai=false;
                break;
            }
        }
        if(avai){
            printf("1\n");
        }else{
            printf("0\n");
        }
        for(i=1;i<=n;i++){
            exist[num[i]]=false;
        }
    }
}