2019年1月22日 星期二

APCS b967: 血緣關係

原題請見 APCS大學程式設計先修檢測 (2016/03/05 實作第四題)
以下為通過高中生程式解題系統 AC (Accepted) 的 C 語言程式參考解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>

#define MAX 100001


int tree[MAX][2]={{0}};
int maxD = 0 ;
int Child_NO[MAX] = {0};
int isChild[MAX] = {0};
int n;

int DFS(int x) {

 if (Child_NO[x] == 0) return 0;//沒有小孩，遞迴中止

 else if (Child_NO[x] == 1)
    {
        for(int j=0 ; j<n-1 ; j++)
         {
            if(tree[j][0]==x)
            {
            return DFS(tree[j][1])+1;//小孩只有一個
            }
         }

    }
 else {//小孩超過兩個以上
        int max1=0 , max2 = 0 ;

   for(int j=0 ; j<n-1 ; j++) {
            if(tree[j][0]==x)
            {
            int dfsresult = DFS(tree[j][1])+1;

    if (dfsresult > max1)
                {
     int tmp = dfsresult;
     dfsresult = max1;
     max1 = tmp;
    }
    if (dfsresult > max2)
    {
     max2 = dfsresult;
    }

   }
  }
  if(maxD<max1+max2) maxD = max1 + max2 ;

  return max1;
 }
}

int main() {

 while(scanf("%d", &n)!=EOF){

  for (int i = 0; i<n-1; i++) {
   scanf("%d %d", &tree[i][0], &tree[i][1]);
   Child_NO[tree[i][0]]+=1;
   isChild[tree[i][1]] = 1;
  }

        int root;
  for (int i = 0; i < n; i++) {//找出root
   if (isChild[i]==0) {//只要不曾經是小孩，就是root
    root = i;
    break;
   }
  }
  int ResultRoot = DFS(root);
     if(ResultRoot > maxD)
        {
           printf("%d",ResultRoot);
        }
        else
        {
         printf("%d", maxD);
        }
        maxD=0;
        ResultRoot=0;
        printf("\n");
 }
return 0;

}
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)