还是并查集的问题,只是数据要注意:
输入0 0,输出yes
迷宫裂开了输出No
#include <stdio.h>
#define MAXN 100001
int p[MAXN],num[MAXN];
int is(int a)
{
if ((num[a]==1)&&(a==p[a])) return 0;
else return 1;
}
int main()
{
int a,b,pa,pb,i,uc,over=0;
for (i=0;i<MAXN;i++)
{
p[i]=i;
num[i]=1;
}
uc=0;
while (scanf("%d%d",&a,&b)&&(a!=-1)&&(b!=-1))
{
if ((!a)&&(!b))
{
if (over || uc>1) printf("No\n");
else printf("Yes\n");
for (i=0;i<MAXN;i++)
{
p[i]=i;
num[i]=1;
}
uc=0;
over=0;
continue;
}
if (!over)
{
pa=a;
pb=b;
while (pa!=p[pa]) pa=p[pa];
while (pb!=p[pb]) pb=p[pb];
}
if (pa==pb)
{
over=1;
}else
if (num[pa]>=num[pb])
{
//printf("is(%d)=%d is(%d)=%d\n",a,is(a),b,is(b));
if ((!is(a))&&(!is(b)))
输入0 0,输出yes
迷宫裂开了输出No
#include <stdio.h>
#define MAXN 100001
int p[MAXN],num[MAXN];
int is(int a)
{
if ((num[a]==1)&&(a==p[a])) return 0;
else return 1;
}
int main()
{
int a,b,pa,pb,i,uc,over=0;
for (i=0;i<MAXN;i++)
{
p[i]=i;
num[i]=1;
}
uc=0;
while (scanf("%d%d",&a,&b)&&(a!=-1)&&(b!=-1))
{
if ((!a)&&(!b))
{
if (over || uc>1) printf("No\n");
else printf("Yes\n");
for (i=0;i<MAXN;i++)
{
p[i]=i;
num[i]=1;
}
uc=0;
over=0;
continue;
}
if (!over)
{
pa=a;
pb=b;
while (pa!=p[pa]) pa=p[pa];
while (pb!=p[pb]) pb=p[pb];
}
if (pa==pb)
{
over=1;
}else
if (num[pa]>=num[pb])
{
//printf("is(%d)=%d is(%d)=%d\n",a,is(a),b,is(b));
if ((!is(a))&&(!is(b)))