题解 P2307 【迷宫】

· · 题解

并查集

这道题简化来说可以这样翻译（每组数据）：

每次输入两个元素：a,b
如果这两个元素在一个集合内，那么对于这组数据，输出0，进入下一组数据
如果不在一个集合内，则合并这两个集合
最后如果只有1个集合输出1，否则输出0

那么这样就很好弄了，code：

#include <cstdio>
#include <cstring>
int f[100001]/*祖先*/,a,b,sum/*集合数量*/;
bool book[100001]/*是否出现*/,flag/*是否违规*/;
void cls(){//初始化
    for(register int i=1;i<=100000;i++) f[i]=i;
    memset(book,0,sizeof(book));sum=0;flag=false;
}
int find(int x){//路径压缩般找祖先
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
int main(){
    cls();
    while(scanf("%d%d",&a,&b)==2)//疯狂输入
    {
        if(a==-1&&b==-1) break;
        if(a==0&&b==0) {printf("%c\n",((!flag&&sum==1)?'1':'0'));cls();continue;}//这组数据结束
        if(!book[a]) sum++;//集合增加
        if(!book[b]) sum++;//集合增加
        book[a]=true;book[b]=true;//标记
        int x1=find(a),x2=find(b);//祖先
        if(x1==x2) flag=true;//标记
        else {sum--;f[x1]=x2;}//修改
    }
    return 0;
}

我觉得这道题可以拓展成最小生成树算法中的Kruskal的一个主要的片段

有兴趣的可以查一下