|
|
赤裸裸的并查集嘛，不過1272還真的坑爹啊，居然0 0輸入也是有效的，真暈了。并查集，好東東，路徑壓縮不錯哈??！ hdu1272(水過)：  
#include<stdio.h>
#include<string.h>
#include<math.h>
int root[100005],b[100005],tot=100000;
int main()
{
int i,x,y,xj,yj,t,tt,flag,tmp;
while (scanf("%d%d",&x,&y)==2&&x!=-1||y!=-1)
{
if (x==0&&y==0)
{
printf("Yes\n");
continue;
}
flag=1;
memset(b,0,sizeof(b));
for (i=1; i<=tot ; i++ )
root[i]=i;
root[y]=x;
b[x]=b[y]=1;
t=1;
while (scanf("%d%d",&x,&y)==2&&x!=0||y!=0)
{
b[x]=b[y]=1;
t++;
xj=x;
while (root[xj]!=xj)
xj=root[xj];
yj=y;
while (root[yj]!=yj)
yj=root[yj];
if (xj==yj)
flag=0;
root[yj]=xj;
while (root[x]!=x)
tmp=x,x=root[x],root[tmp]=xj;
while (root[y]!=y)
tmp=y,y=root[y],root[tmp]=xj;
}
for (i=1; i<=tot ; i++ )
t-=b[i];
if (flag&&t==-1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
hdu1232（水過）：
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,m,root[1005];
int main()
{
int i,x,y,xj,yj,ans,t;
while (scanf("%d%d",&n,&m)==2)
{
for (i=1;i<=n ;i++ )
root[i]=i;
for (i=1;i<=m ;i++ )
{
scanf("%d%d",&x,&y);
xj=x;
while (root[xj]!=xj)
xj=root[xj];
yj=y;
while (root[yj]!=yj)
yj=root[yj];
if (xj!=yj)
root[xj]=yj;
while (root[x]!=x)
t=x,root[x]=yj,x=root[t];
while (root[y]!=y)
t=y,root[y]=yj,y=root[t];
}
ans=0;
for (i=1;i<=n ;i++ )
if (root[i]==i)
ans++;
printf("%d\n",ans-1);
}
return 0;
}
嗯，今天效率低啊，就兩排序一并查集。哎，呀哦加油；
|