APCS 實作題 10503 - 4 血緣關係

李泳霖

b967: 第 4 題 血緣關係

APCS 實作題 10503 - 4

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. import java.util.ArrayList;
   
4. 
   
5. 
   
6. public class P4 {
   
7.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//輸入物件
   
8.         int n,root;//n為總共有多少節點,root為根結點
   
9.         Node node[];//宣告陣列
   
10.         String str,raw[];//str為幾個節點輸入用,raw為輸入關係用
    
11.         int res,finalMaxChildDis;
    
12.         P4()throws Exception//建構子
    
13.         {
    
14.                 while((str=br.readLine())!=null)
    
15.                 {
    
16.                         finalMaxChildDis=-1;//紀錄最遠親戚的距離
    
17.                         n=Integer.parseInt(str);//有n個節點
    
18.                         node=new Node[n];//宣告陣列長度
    
19.                         for(int i=0;i<n;i++)
    
20.                                 node[i]=new Node();//建立n個物件
    
21.                         for(int i=0; i<n-1; i++)
    
22.                         {
    
23.                                 //連續輸入2個值，表示父與子,空白擷取
    
24.                                 raw=br.readLine().split(" ");
    
25. 
    
26.                                 //raw[0]是父，因是字串所以做轉型，給p存
    
27.                                 int p=Integer.parseInt(raw[0]);
    
28. 
    
29.                                 //raw[1]是子，因是字串所以做轉型，給c存
    
30.                                 int c=Integer.parseInt(raw[1]);
    
31. 
    
32.                                 //node[c]的父為p;
    
33.                                 node[c].parent=p;
    
34. 
    
35.                                 //node[p]的子為c;
    
36.                                 node[p].child.add(c);
    
37.                         }
    
38. 
    
39.                         //找根結點、以及找尋每個節點到葉節點的深度
    
40.                         for(int i=0;i<n;i++)
    
41.                         {
    
42.                                 if(node[i].parent==-1)
    
43.                                         //當節點的父親為-1表示此節點為父
    
44.                                         root=i;
    
45. 
    
46.                                 //從沒有小孩的節點開始往上推高度
    
47.                                 if(node[i].child.size()==0)
    
48.                                 {
    
49.                                         //h為此節點到最後葉節點的深度,初始為0
    
50.                                         int h=0;
    
51.                                         //偵測此節點的父親為誰
    
52.                                         int parent=node[i].parent;
    
53.                                         //如推到最後節點為-1了表示到根結點了
    
54.                                         while(parent!=-1)
    
55.                                         {
    
56.                                                 h++;//深度加一
    
57. 
    
58.                                                 //比較看看h是否有大於目前節點已經有的深度紀錄(因有左右兩邊)
    
59.                                                 if(h>node[parent].h)
    
60.                                                 {
    
61.                                                         //更新目前節點到葉節點的深度
    
62.                                                         node[parent].h=h;
    
63.                                                 }
    
64.                                                 else
    
65. 
    
66.                                                         //若h<目前節點的h，表示不用更新，直接跳出迴圈
    
67.                                                         break;
    
68. 
    
69.                                                 //繼續往上找
    
70.                                                 parent=node[parent].parent;
    
71.                                         }
    
72.                                 }
    
73.                         }
    
74.                         //開始抓取節點到節點的距離
    
75.                         for(int i=0;i<n;i++)
    
76.                         {
    
77.                                 if(node[i].child.size()>=2)
    
78.                                 {
    
79.                                         for(int j=0;j<node[i].child.size();j++)
    
80.                                         {
    
81.                                                 int childH=node[node[i].child.get(j)].h;
    
82.                                                 if(childH>node[i].max)
    
83.                                                 {
    
84.                                                         node[i].sec=node[i].max;
    
85.                                                         node[i].max=childH;
    
86.                                                 }
    
87.                                                 else if(childH>node[i].sec)
    
88.                                                         node[i].sec=childH;
    
89. 
    
90.                                         }
    
91.                                         node[i].maxChildDis=node[i].max+node[i].sec+2;
    
92. 
    
93.                                         //判斷是否有大於其他節點之孩子間的最深距離
    
94.                                         if(node[i].maxChildDis>finalMaxChildDis)
    
95.                                                 //更新血緣關係的距離
    
96.                                                 finalMaxChildDis=node[i].maxChildDis;
    
97.                                 }
    
98.                         }
    
99. 
    
100.                 }
     
101.         }
     
102.         class Node{
     
103.                 int parent=-1,h=0;
     
104.                 int maxChildDis=-1,max=-1,sec=-1;
     
105.                 ArrayList<Integer>child=new ArrayList<Integer>();
     
106.         }
     
107.         public static void main(String[] args)throws Exception {
     
108.                 // TODO 自動產生的方法 Stub
     
109.                 new P4();
     
110.         }
     
111. 
     
112. }
     
113. /*
     
114. 8
     
115. 0 1
     
116. 0 2
     
117. 0 3
     
118. 7 0
     
119. 1 4
     
120. 1 5
     
121. 3 6
     
122. 
     
123. 6
     
124. 3 5
     
125. 0 1
     
126. 3 4
     
127. 1 2
     
128. 1 3
     
129. */
     
130. 
     
131. }

複製代碼