题解 P2307 【迷宫】

· · 题解

简化题意：给你t个无向图，依次判断它们是不是一棵完整的树

那如何判断一个无向图是不是一棵树呢？

很简单，若n个点之间有且仅有n-1条边，并且这n个点之间无环，那么这n个点组成一棵树。

划重点：n-1条边、无环

一.判断是否有n-1条边

由于每组数据都会依次给出两个点的编号，表示这两个点之间有一条边。

那我们用一个桶计算出点的个数，再用一个计数器记录连了多少条边。

判断一下边数是否等于点数-1即可。

二.判断是否有环

可以借鉴一下kruscal算法连边时判断是否形成环的方法。

用并查集维护点与点之间的联系。

每次连边时，判断两个端点是否在一个集合内。

如果在同一集合中，说明这两点已经有路径，再连边就会产生环。因此直接输出0即可。

如果不在同一集合中，说明这两点之间没有路径，可以连边。

OK，接下来是代码环节：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

inline int read(){//普通快读优化，萌新可换成cin
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int maxn=100010;//定义数组大小
int a[maxn]; //a数组是并查集
bool flag;//flag用来记录是否出现-1,-1

int fin(int x){//查找祖先&路径压缩
    if(a[x]==0) return x;
    else return a[x]=fin(a[x]);
}

inline void check(){//判断每组数据是否是树并输出相应的答案
    memset(a,0,sizeof(a));//先清零并查集
    bool f=0;//f用来记录图中是否出现了环
    int b[maxn]={0},cnt1=0,cnt2=0,x,y,xx,yy;
    //b数组是桶，cnt1是点数，cnt2是边数 
    //x和y是连边的两点，xx和yy是两点的祖先
    while(1){//循环输入
        x=read();y=read();
        if(x==0&&y==0) break;//0,0表明输入结束
        if(x==-1&&y==-1){//-1,-1表明所有数据都已输入完
            flag=1;//flag记录一下
            return;//直接返回主函数
        }
        if(f) continue;
        //已经有环了，那就不用再进行操作了
        //这里是为了节省空间，因为还得把剩下的数据输入
        //如果不用f标记的话必须得用数组存储
        xx=fin(x);yy=fin(y);//查找祖先
        if(xx!=yy){//祖先不同，不在同一集合中
            a[xx]=yy;//连边
            if(!b[x]){//x这个点之前没出现过
                b[x]=1;//修改桶
                cnt1++;//点数+1
            }
            if(!b[y]){//同上
                b[y]=1;
                cnt1++;
            }
            cnt2++;//又连了一条边，因此边数要+1
        }else{//祖先相同，在同一集合中
            f=1;//出现了环，更改f标记
        }
    }
    if(cnt2==cnt1-1&&!f) printf("1\n");
    //边数是点数-1且无环，是树，输出1
    else printf("0\n");
    //否则不是树，输出0
    return;
} 

int main(){
    while(1){
        check();
        if(flag) break;
        //出现了-1，-1，所有数据已输入完毕，跳出循环
    }
    return 0;
}

你AC了没？AC了就给个赞呗。