APCS c463: 樹狀圖分析 (Tree Analyses)

原題請見 APCS大學程式設計先修檢測 (2017/10/18 實作第三題)
以下為通過高中生程式解題系統 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

#include <stdio.h> #include <stdlib.h> #define MAX 100001 void main(){ int i,j,n,m; long long int most_hi=0; //最大高度 int parent[MAX]={0}; //記錄節點的父節點 int k[MAX]={0};//每個節點的子節點數量 int h[MAX]={0}; //每個節點的高度 scanf(" %d",&n); //輸入節點個數 for(i=1 ; i<=n ; i++){ scanf(" %d",&k[i]); //每個節點的子節點個數 for(j=1 ; j<=k[i] ; j++) { scanf(" %d",&m); parent[m]=i; //記錄節點的父節點 } } for(i=1 ; i<=n ; i++) { if(parent[i]==0) printf("%d",i); } for(i=1 ; i<=n ; i++) { if(k[i]==0) { int height=0; //高度 int tmp = parent[i]; //換 i 的父節點 while(tmp!=0) { height++; if(height>h[tmp]){ h[tmp]=height; } tmp=parent[tmp]; } } } for(i=1 ; i<=n ; i++) { most_hi = most_hi + h[i]; } printf("\n%lld",most_hi); }