hdu 1272小希の迷宮
2505 ワード
タイトルの説明:
任意のグループを入力し、2つの接続されたデータを入力し、最後に0,0で終わり、すべての点が1本の木にあるかどうかを判断し、リングを構成しません.
このテーマで注意すべきは、0,0を入力すると問題の意味に合致するはずです.
1,2,2,1,0,0を入力した場合は,問題の意味に合致しないループを構成する.
入力は必ずしも1からでも連続した入力でもない
hdu oj上でいつもWAを提出する時c++をg++に変えてaになるかもしれません
任意のグループを入力し、2つの接続されたデータを入力し、最後に0,0で終わり、すべての点が1本の木にあるかどうかを判断し、リングを構成しません.
このテーマで注意すべきは、0,0を入力すると問題の意味に合致するはずです.
1,2,2,1,0,0を入力した場合は,問題の意味に合致しないループを構成する.
入力は必ずしも1からでも連続した入力でもない
hdu oj上でいつもWAを提出する時c++をg++に変えてaになるかもしれません
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 100005
int pre[MAXN], vis[MAXN];
int jishu = 0; //
int find(int n)
{
return n == pre[n] ? n : pre[n] = find(pre[n]); //
}
int unionFri(int x,int y) //
{
int findX = find(x); //
int findY = find(y);
if(findX != findY) //
{
pre[findX] = findY;
jishu++; // +1 i
}
return jishu;
}
int main()
{
int m,n;
int i=0;
int sum;
for(int i=1;i<MAXN;i++)
pre[i] = i; //
memset(vis, 0 ,sizeof(vis));
while(scanf("%d%d",&m,&n)&&m!=-1&&n!=-1)
{
if (i == 0 && m == 0 && n == 0) // 0,0 yes
{
puts("Yes");
continue;
}
if(m && n) //
{
i++; // ++
vis[m] = vis[n] = 1; // 1
sum = unionFri(m,n); //
}
else
{
if(i == sum) //
{
int k =0, tmp = -1; //tmp
for(int j=1;j<MAXN;j++) //
if (vis[j]) //
{
if (tmp == -1) //
tmp = find(j);//
else if (tmp!=find(j)) // ++
{
k++;
break;
}
}
if(k == 0)
printf("Yes
");
else
printf("No
");
}
else
printf("No
"); // no
i=0;//
jishu = 0;
for(int i=1;i<MAXN;i++)
pre[i] = i;
memset(vis, 0 ,sizeof(vis));
}
}
return 0;
}