首页 > 代码库 > hdu 1325 is it a tree?

hdu 1325 is it a tree?

2024-11-13 08:30:02   203人阅读

网上一搜全是并查集。。 并查集POJ可以水过，HDU就不行了。。

并查集的话：

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int pre[1005]; 6 bool vis[1005]; 7 int num[1005]; 8 bool flag; 9 int x,y,icase=1;10 void init()11 {12     for(int i=0;i<=1000;i++)13         pre[i]=i;14     memset(num,0,sizeof(num));15     memset(vis,false,sizeof(vis));16     flag=false;17 }18 int find(int x)19 {20     if(pre[x]!=x)21         pre[x]=find(pre[x]);22     return pre[x];23 }24 void judge()25 {26     for(int i=1;i<=1000;i++)27         if(vis[i]) num[find(i)]++;28     int key=0;29     for(int i=1;i<=1000;i++)30         if(num[i]>1) key++;31     if(key>1) flag=true;32 }33 int main()34 {35 //    freopen("in.txt","r",stdin);36     init();37     while(1)38     {39         scanf("%d%d",&x,&y);40         if(x<0 && y<0)41             break;42         else if(x==0 && y==0)43         {44             judge();45             if(flag)46                 printf("Case %d is not a tree.\n",icase++);47             else48                 printf("Case %d is a tree.\n",icase++);49             init();50             continue;51         }52         else53         {54             vis[x]=vis[y]=true;55             if(find(x)==find(y) || pre[y]!=y)56                 flag=true;57             else58                 pre[y]=x;59         }60     }61     return 0;62 }
迪哥代码

 

有个坑是只要是输入两个负数就结束，不一定是-1 -1

判断图是否为树：1.是否为连通图  2.是否有环

因为题目给的是从父亲指向儿子，所以直接判断点的入度就可以了

 1 #include "iostream" 2 #include "memory.h" 3 #include "cstdio" 4 using namespace std; 5 #define MAXN 1111 6 int fa[MAXN]; 7 int in_degree[MAXN]; 8 bool c[MAXN]; 9 bool ok;10 11 int main()12 {13     int a,b,T = 1;14     while (~scanf("%d%d",&a,&b)) {15         memset(fa,-1,sizeof(fa));16         memset(in_degree,0,sizeof(in_degree));17         memset(c,0,sizeof(c));18         if (a < 0 && b < 0) break;19         c[a] = 1;20         c[b] = 1;21         in_degree[b]++;22         while (~scanf("%d%d",&a,&b),a+b) {23             if (a < 0 && b < 0) return 0;24             in_degree[b]++;25             c[a] = 1;26             c[b] = 1;27         }28         int re = 0;29         int ok = 1;30         for (int i = 0;i < MAXN; ++ i) if (c[i]){31             if (in_degree[i] == 0) re ++;32             if (in_degree[i] > 1) ok = 0;33         }34         if (re == 1 && ok) printf("Case %d is a tree.\n",T);35         else printf("Case %d is not a tree.\n",T);36         T++;37     }38     return 0;39 }

 

hdu 1325 is it a tree?


联系
我们