hdu 1272 小希的迷宫
http://acm.hdu.edu.cn/showproblem.php?pid=1272
整个文件以两个-1结尾。
题目大意:小希要做一个迷宫,迷宫中任意两个房间有且仅有一条路径可以相通(除非走了回头路)。
这样,就需要用到并查集了(赤裸裸的),对于输入的两个顶点,判断是否在同一个集合内,是的话,就是存在多条通路了,而对于一个迷宫,所有的点最后必须在同一个集合内(这一个问题刚开始没有考虑到,贡献了两次WA),处理好这两个问题,就可以了
有一个比较特殊的情况,就是输入的那一组数据只有两个0,必须输出 Yes
网上有很多人写了这个题目的解题报告,但大家都是用一个数组来记录是否用过,然后对用过的点进行寻根,最后看一下是不是所有有用过的点都是同一个根,我觉得没有必要,只要记录点是否用过,最后,连接的边和用到的点的差是1就可以了,也就是说连接n个点,只要n-1条边,so~~
#include<iostream>
using namespace std;
#define MAX 100001
bool mark[MAX];
int parent[MAX];
int findp(int a)
{
while(a!=parent[a])
a=parent[a];
return a;
}
bool merge(int a,int b)
{
int x=findp(a);
int y=findp(b);
if(x==y)
return 0;
parent[y]=x;
return 1;
}
int main()
{
int x,y;
while(~scanf("%d%d",&x,&y))
{
if(!x&&!y)
{
puts("Yes");
continue;
}
if(x==-1&&y==-1)
break;
int i;
for(i=1;i<MAX;i++)
parent[i]=i;
memset(mark,0,sizeof(mark));
mark[x]=mark[y]=1;
merge(x,y);
int n=1,flag=1;
while(~scanf("%d%d",&x,&y))
{
if(!x&&!y)
break;
if(!mark[x])
{
n++;
mark[x]=1;
}
if(!mark[y])
{
n++;
mark[y]=1;
}
if(merge(x,y))
n--;
else
flag=0;
}
if(flag&&n==1)
puts("Yes");
else
puts("No");
}
return 0;
}
我觉得广搜也可以 不过效率明显没有第一种高 不过还是贴一下我的代码
思路:当广度搜索到一个搜索过了的点,并且不是父亲结点时,就是个环
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[100001];
int parent[100001];
int bfs(int pos)
{
queue<int> q;
q.push(pos);
int d,i;
for(i=1;i<=100000;i++)
parent[i]=i;
parent[pos]=-1;
while(!q.empty())
{
d=q.front();
q.pop();
for(i=0;i<v[d].size();i++)
{
if(v[d][i]==parent[d])
continue;
if(parent[v[d][i]]==v[d][i])
{
parent[v[d][i]]=d;
q.push(v[d][i]);
}
else
return 0;
}
}
return 1;
}
int findp(int a)
{
while(a!=parent[a])
a=parent[a];
return a;
}
int main()
{
int x,y,i;
while(~scanf("%d%d",&x,&y))
{
if(x==-1&&y==-1)
break;
for(i=1;i<100001;i++)
v[i].clear();
int pos=x;
v[x].push_back(y);
v[y].push_back(x);
if(!x&&!y)
{
puts("Yes");
continue;
}
for(i=1;i<=100000;i++)
parent[i]=i;
parent[y]=x;
int xx,yy;
int mark[100001]={0};
mark[x]=mark[y]=1;
int num=2;
if(x==y)
num=1;
while(1)
{
scanf("%d%d",&x,&y);
if(!x&&!y)
break;
v[x].push_back(y);
v[y].push_back(x);
xx=findp(x);
yy=findp(y);
if(xx!=yy)
parent[yy]=xx;
if(!mark[x])
{
num++;
mark[x]=1;
}
if(!mark[y])
{
num++;
mark[y]=1;
}
}
int count=0;
for(i=1;i<=100000;i++)
if(parent[i]!=i)
count++;
if(count!=num-1)
{
puts("No");
continue;
}
if(bfs(pos))
puts("Yes");
else
puts("No");
}
return 0;
}