本帖最後由 李泳霖 於 2022-5-21 09:16 編輯
b967: 第 4 題 血緣關係
APCS 實作題 10503 - 4
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- public class P4 {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//輸入物件
- int n,root;//n為總共有多少節點,root為根結點
- Node node[];//宣告陣列
- String str,raw[];//str為幾個節點輸入用,raw為輸入關係用
- int res,finalMaxChildDis;
- P4()throws Exception//建構子
- {
- while((str=br.readLine())!=null)
- {
- finalMaxChildDis=-1;//紀錄最遠親戚的距離
- n=Integer.parseInt(str);//有n個節點
- node=new Node[n];//宣告陣列長度
- for(int i=0;i<n;i++)
- node[i]=new Node();//建立n個物件
- for(int i=0; i<n-1; i++)
- {
- //連續輸入2個值,表示父與子,空白擷取
- raw=br.readLine().split(" ");
- //raw[0]是父,因是字串所以做轉型,給p存
- int p=Integer.parseInt(raw[0]);
- //raw[1]是子,因是字串所以做轉型,給c存
- int c=Integer.parseInt(raw[1]);
- //node[c]的父為p;
- node[c].parent=p;
- //node[p]的子為c;
- node[p].child.add(c);
- }
- //找根結點、以及找尋每個節點到葉節點的深度
- for(int i=0;i<n;i++)
- {
- if(node[i].parent==-1)
- //當節點的父親為-1表示此節點為父
- root=i;
- //從沒有小孩的節點開始往上推高度
- if(node[i].child.size()==0)
- {
- //h為此節點到最後葉節點的深度,初始為0
- int h=0;
- //偵測此節點的父親為誰
- int parent=node[i].parent;
- //如推到最後節點為-1了表示到根結點了
- while(parent!=-1)
- {
- h++;//深度加一
- //比較看看h是否有大於目前節點已經有的深度紀錄(因有左右兩邊)
- if(h>node[parent].h)
- {
- //更新目前節點到葉節點的深度
- node[parent].h=h;
- }
- else
- //若h<目前節點的h,表示不用更新,直接跳出迴圈
- break;
- //繼續往上找
- parent=node[parent].parent;
- }
- }
- }
- //開始抓取節點到節點的距離
- for(int i=0;i<n;i++)
- {
- if(node[i].child.size()>=2)
- {
- for(int j=0;j<node[i].child.size();j++)
- {
- int childH=node[node[i].child.get(j)].h;
- if(childH>node[i].max)
- {
- node[i].sec=node[i].max;
- node[i].max=childH;
- }
- else if(childH>node[i].sec)
- node[i].sec=childH;
- }
- node[i].maxChildDis=node[i].max+node[i].sec+2;
- //判斷是否有大於其他節點之孩子間的最深距離
- if(node[i].maxChildDis>finalMaxChildDis)
- //更新血緣關係的距離
- finalMaxChildDis=node[i].maxChildDis;
- }
- }
- }
- }
- class Node{
- int parent=-1,h=0;
- int maxChildDis=-1,max=-1,sec=-1;
- ArrayList<Integer>child=new ArrayList<Integer>();
- }
- public static void main(String[] args)throws Exception {
- // TODO 自動產生的方法 Stub
- new P4();
- }
- }
- /*
- 8
- 0 1
- 0 2
- 0 3
- 7 0
- 1 4
- 1 5
- 3 6
- 6
- 3 5
- 0 1
- 3 4
- 1 2
- 1 3
- */
- }
複製代碼 |