返回列表 發帖

樹狀圖 (一) - 無分岔點

本帖最後由 李泳霖 於 2022-4-16 10:14 編輯

樹狀圖分析的其中一種方法為 深度優先搜尋演算法 (DFS),我們可利用此演算法來找出樹狀結構中,節點間的關係以及自根部開始最深的距離。

但在程式競賽或APCS檢定中若遇到類似的題目,老師並不建議使用 DFS 來解題。原因是 DFS 為遞迴的結構,遞迴結構在對效率極度要求的程式競賽或APCS檢定中,非常容易發生 StackOverFlowError、TLE、MLE 等疑難雜症。

因此對於樹狀圖分析這類的考題,老師會帶同學們以從葉節點往根節點走訪的思維來解題。當然,依然會提供 DFS 解法的程式碼給同學們參考。

下面的這個例子為一無分岔點的樹狀圖,輸入分為兩部分,第一部分為共有幾個成員,第二部分為所有關係。請同學們試著找出在這樣的一個樹狀結構中,根節點是誰、葉節點是誰、最深的距離是多少?

範例輸入

6
0 3
1 0
5 4
2 1
3 5

範例輸出

根節點: 2
葉節點: 4
最深距離: 5



  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

  4. public class P1 {
  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  6.         String raw[];
  7.         int n,root,leaf;
  8.         Node node[];
  9.         P1() throws Exception{
  10.                 n=Integer.parseInt(br.readLine());
  11.                 node=new Node[n];
  12.                 for(int i=0; i<n; i++)
  13.                         node[i]=new Node();
  14.                 for(int i=0; i<n-1; i++){
  15.                         raw=br.readLine().split(" ");
  16.                         int p=Integer.parseInt(raw[0]);
  17.                         int c=Integer.parseInt(raw[1]);
  18.                         node[c].parent=p;
  19.                         node[p].child=c;
  20.                 }               
  21.                 for(int i=0; i<n; i++){
  22.                         System.out.println(i+"'s parent:"+node[i].parent);
  23.                         System.out.println(i+"'s child:"+node[i].child);
  24.                 }
  25.         }
  26.        
  27.         public static void main(String[] args) throws Exception {
  28.                 new P1();
  29.         }
  30. }
  31. class Node{
  32.         int parent=-1, child=-1, n=0;
  33. }
複製代碼

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見
Vincent

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見

TOP

此帖僅作者可見
Jian-wei Wang

TOP

此帖僅作者可見

TOP

返回列表