返回列表 發帖

APCS 實作題 10503 - 4 血緣關係

本帖最後由 李泳霖 於 2022-5-21 09:16 編輯

b967: 第 4 題 血緣關係

APCS 實作題 10503 - 4



  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;


  4. public class P4 {
  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//輸入物件
  6.         int n,root;//n為總共有多少節點,root為根結點
  7.         Node node[];//宣告陣列
  8.         String str,raw[];//str為幾個節點輸入用,raw為輸入關係用
  9.         int res,finalMaxChildDis;
  10.         P4()throws Exception//建構子
  11.         {
  12.                 while((str=br.readLine())!=null)
  13.                 {
  14.                         finalMaxChildDis=-1;//紀錄最遠親戚的距離
  15.                         n=Integer.parseInt(str);//有n個節點
  16.                         node=new Node[n];//宣告陣列長度
  17.                         for(int i=0;i<n;i++)
  18.                                 node[i]=new Node();//建立n個物件
  19.                         for(int i=0; i<n-1; i++)
  20.                         {
  21.                                 //連續輸入2個值,表示父與子,空白擷取
  22.                                 raw=br.readLine().split(" ");

  23.                                 //raw[0]是父,因是字串所以做轉型,給p存
  24.                                 int p=Integer.parseInt(raw[0]);

  25.                                 //raw[1]是子,因是字串所以做轉型,給c存
  26.                                 int c=Integer.parseInt(raw[1]);

  27.                                 //node[c]的父為p;
  28.                                 node[c].parent=p;

  29.                                 //node[p]的子為c;
  30.                                 node[p].child.add(c);
  31.                         }

  32.                         //找根結點、以及找尋每個節點到葉節點的深度
  33.                         for(int i=0;i<n;i++)
  34.                         {
  35.                                 if(node[i].parent==-1)
  36.                                         //當節點的父親為-1表示此節點為父
  37.                                         root=i;

  38.                                 //從沒有小孩的節點開始往上推高度
  39.                                 if(node[i].child.size()==0)
  40.                                 {
  41.                                         //h為此節點到最後葉節點的深度,初始為0
  42.                                         int h=0;
  43.                                         //偵測此節點的父親為誰
  44.                                         int parent=node[i].parent;
  45.                                         //如推到最後節點為-1了表示到根結點了
  46.                                         while(parent!=-1)
  47.                                         {
  48.                                                 h++;//深度加一

  49.                                                 //比較看看h是否有大於目前節點已經有的深度紀錄(因有左右兩邊)
  50.                                                 if(h>node[parent].h)
  51.                                                 {
  52.                                                         //更新目前節點到葉節點的深度
  53.                                                         node[parent].h=h;
  54.                                                 }
  55.                                                 else

  56.                                                         //若h<目前節點的h,表示不用更新,直接跳出迴圈
  57.                                                         break;

  58.                                                 //繼續往上找
  59.                                                 parent=node[parent].parent;
  60.                                         }
  61.                                 }
  62.                         }
  63.                         //開始抓取節點到節點的距離
  64.                         for(int i=0;i<n;i++)
  65.                         {
  66.                                 if(node[i].child.size()>=2)
  67.                                 {
  68.                                         for(int j=0;j<node[i].child.size();j++)
  69.                                         {
  70.                                                 int childH=node[node[i].child.get(j)].h;
  71.                                                 if(childH>node[i].max)
  72.                                                 {
  73.                                                         node[i].sec=node[i].max;
  74.                                                         node[i].max=childH;
  75.                                                 }
  76.                                                 else if(childH>node[i].sec)
  77.                                                         node[i].sec=childH;

  78.                                         }
  79.                                         node[i].maxChildDis=node[i].max+node[i].sec+2;

  80.                                         //判斷是否有大於其他節點之孩子間的最深距離
  81.                                         if(node[i].maxChildDis>finalMaxChildDis)
  82.                                                 //更新血緣關係的距離
  83.                                                 finalMaxChildDis=node[i].maxChildDis;
  84.                                 }
  85.                         }

  86.                 }
  87.         }
  88.         class Node{
  89.                 int parent=-1,h=0;
  90.                 int maxChildDis=-1,max=-1,sec=-1;
  91.                 ArrayList<Integer>child=new ArrayList<Integer>();
  92.         }
  93.         public static void main(String[] args)throws Exception {
  94.                 // TODO 自動產生的方法 Stub
  95.                 new P4();
  96.         }

  97. }
  98. /*
  99. 8
  100. 0 1
  101. 0 2
  102. 0 3
  103. 7 0
  104. 1 4
  105. 1 5
  106. 3 6

  107. 6
  108. 3 5
  109. 0 1
  110. 3 4
  111. 1 2
  112. 1 3
  113. */

  114. }
複製代碼

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見
Jian-wei Wang

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見
Vincent

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

返回列表