poj1308
#include<stdio.h>
#include<string.h>//判断是否有环，判断是否是一个根节点。判断空树的情况
#define N 1000000
int pre[N+10],dis[N+10],degree[N+10];
int find(int n) {
return pre[n]=n==pre[n]?n:find(pre[n]);
}
int main() {
int a,b,cnt,flag,f1,f2,i,min,max,k=0,w,u;
while(scanf("%d%d",&a,&b),a!=-1||b!=-1) {
if(a==0&&b==0) {//和杭电不一样他是一个树刚开始错在这
printf("Case %d is a tree.\n",++k);
continue;
}
for(i=1;i<=N;i++)
pre[i]=i;
f1=find(a);
f2=find(b);
degree[a]++;
pre[f2]=f1;
dis[a]=dis[b]=1;
min=a>b?b:a;
max=a>b?a:b;
w=0;
if(min==max)//与节点自身相连不是一棵树
w=1;
flag=0;
while(scanf("%d%d",&a,&b),a||b) {
degree[a]++;
if(a==b)
w=1;
f1=find(a);
f2=find(b);
if(f1==f2)
flag=1;
else
pre[f2]=f1;
dis[a]=dis[b]=1;
min=min<a?min:a;
min=min<b?min:b;
max=max>a?max:a;
max=max>b?max:b;
}
if(flag||w) {
printf("Case %d is not a tree.\n",++k);
continue;
}
cnt=0;u=0;
/* for(i=min;i<=max;i++)
if(degree[i]>cnt)
cnt=degree[i];
for(i=min;i<=max;i++)
if(cnt==degree[i])
u++;
if(u>1) {
printf("Case %d is not a tree.\n",++k);
continue;
}*/
cnt=0;
for(i=min;i<=max;i++)
if(pre[i]==i&&dis[i])
cnt++;
if(cnt==1)
printf("Case %d is a tree.\n",++k);
else
printf("Case %d is not a tree.\n",++k);
}
return 0;
}//测试数据1: 0 0 空树是一棵树
//2: 1 1 0 0 不是树 不能自己指向自己
//3: 1 2 1 2 0 0 不是树....自己开始一直在这么WA 好郁闷 重复都不行呀~~5555
//4: 1 2 2 3 4 5 不是树 森林不算是树(主要是注意自己)
//5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 注意 一个节点在指向自己的父亲或祖先 都是错误的 即 9-->1 错
//6: 1 2 2 1 0 0 也是错误的
优质内容筛选与推荐>>
1、LeetCode13.罗马数字转整数
2、【转载】复制文件到已存在的Jar
3、Java开发中对Redis的基本操作
4、Struts2中通过Ajax传递json数据
5、经典算法系列三----堆排序
#include<string.h>//判断是否有环，判断是否是一个根节点。判断空树的情况
#define N 1000000
int pre[N+10],dis[N+10],degree[N+10];
int find(int n) {
return pre[n]=n==pre[n]?n:find(pre[n]);
}
int main() {
int a,b,cnt,flag,f1,f2,i,min,max,k=0,w,u;
while(scanf("%d%d",&a,&b),a!=-1||b!=-1) {
if(a==0&&b==0) {//和杭电不一样他是一个树刚开始错在这
printf("Case %d is a tree.\n",++k);
continue;
}
for(i=1;i<=N;i++)
pre[i]=i;
f1=find(a);
f2=find(b);
degree[a]++;
pre[f2]=f1;
dis[a]=dis[b]=1;
min=a>b?b:a;
max=a>b?a:b;
w=0;
if(min==max)//与节点自身相连不是一棵树
w=1;
flag=0;
while(scanf("%d%d",&a,&b),a||b) {
degree[a]++;
if(a==b)
w=1;
f1=find(a);
f2=find(b);
if(f1==f2)
flag=1;
else
pre[f2]=f1;
dis[a]=dis[b]=1;
min=min<a?min:a;
min=min<b?min:b;
max=max>a?max:a;
max=max>b?max:b;
}
if(flag||w) {
printf("Case %d is not a tree.\n",++k);
continue;
}
cnt=0;u=0;
/* for(i=min;i<=max;i++)
if(degree[i]>cnt)
cnt=degree[i];
for(i=min;i<=max;i++)
if(cnt==degree[i])
u++;
if(u>1) {
printf("Case %d is not a tree.\n",++k);
continue;
}*/
cnt=0;
for(i=min;i<=max;i++)
if(pre[i]==i&&dis[i])
cnt++;
if(cnt==1)
printf("Case %d is a tree.\n",++k);
else
printf("Case %d is not a tree.\n",++k);
}
return 0;
}//测试数据1: 0 0 空树是一棵树
//2: 1 1 0 0 不是树 不能自己指向自己
//3: 1 2 1 2 0 0 不是树....自己开始一直在这么WA 好郁闷 重复都不行呀~~5555
//4: 1 2 2 3 4 5 不是树 森林不算是树(主要是注意自己)
//5: 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 注意 一个节点在指向自己的父亲或祖先 都是错误的 即 9-->1 错
//6: 1 2 2 1 0 0 也是错误的
优质内容筛选与推荐>>
1、LeetCode13.罗马数字转整数
2、【转载】复制文件到已存在的Jar
3、Java开发中对Redis的基本操作
4、Struts2中通过Ajax传递json数据
5、经典算法系列三----堆排序