摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:很多

我採用暴力+BFS尋訪
我個人認為應該不用 不過我想不到別的方式 網友提供唄

/**我的做法不好**********************************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n,m,time=1,a,b,c;
 char map[20][20]={0},max=-1,min=100,flag[50]={0};
 while(scanf("%d %d",&n,&m)==2&&n>=0&&m>=0)
  {
    if(n==0&&m==0)
     {
      printf("Case %d ",time++);
      int find=0,no=0;
      for(a=min;a<=max;a++)        /*判定雙向的*/
       {
        if(flag[a]==0) continue;
        for(b=min;b<=max;b++)
         {
          if(flag[b]==0) continue;
          if(map[a][b]==1&&map[b][a]==1) no=1;
         }
       }
      for(a=min;a<=max;a++)     /*判定連結不超過1個*/
       {
        if(flag[a]==0) continue;
        for(b=min;b<=max;b++)
         {
          if(flag[b]==0) continue;
          if(map[a][b]==1) {find++;}
         }
         if(find>1) {no=1;break;}
         find=0;
       } 
      for(a=min;a<=max;a++)      /*將所有路改成雙向*/
       for(b=min;b<=max;b++)
        if(map[a][b]==1) map[b][a]=1;
      char queue[50]={0},flag2[50]={0},top=0;/*是否能探訪所有點 一顆樹!! 可能會產生2顆以上的樹*/
      queue[0]=min;
       for(a=0;a<=top;a++)
        {
         int nn=queue[a];
         for(b=min;b<=max;b++)
          if(map[nn][b]==1&&flag2[b]==0) {top++;queue[top]=b;flag2[b]=1;}
        }
      for(a=min;a<=max;a++)
       if(flag[a]!=flag2[a]) {no=1;break;}
      if(no==1) printf("is not a tree.\n");
      else printf("is a tree.\n");
      for(a=min;a<=max;a++)
       for(b=min;b<=max;b++)
        map[a][b]=0;
      for(a=min;a<=max;a++) flag[a]=0;  
       max=-1;min=100;
     }
    else
     {
      if(n>max) max=n;
      if(m>max) max=m;
      if(n<min) min=n;
      if(m<min) min=m;
      flag[m]=1;flag[n]=1;
      map[m][n]++;/*m連結到n*/
     }
  }
 return 0;
}