標題:
樹狀圖 (一) - 無分岔點
[打印本頁]
作者:
李泳霖
時間:
2022-4-2 11:22
標題:
樹狀圖 (一) - 無分岔點
本帖最後由 李泳霖 於 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P1 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int n,root,leaf;
Node node[];
P1() throws Exception{
n=Integer.parseInt(br.readLine());
node=new Node[n];
for(int i=0; i<n; i++)
node[i]=new Node();
for(int i=0; i<n-1; i++){
raw=br.readLine().split(" ");
int p=Integer.parseInt(raw[0]);
int c=Integer.parseInt(raw[1]);
node[c].parent=p;
node[p].child=c;
}
for(int i=0; i<n; i++){
System.out.println(i+"'s parent:"+node[i].parent);
System.out.println(i+"'s child:"+node[i].child);
}
}
public static void main(String[] args) throws Exception {
new P1();
}
}
class Node{
int parent=-1, child=-1, n=0;
}
複製代碼
作者:
李泳霖
時間:
2022-4-2 11:23
此帖僅作者可見
作者:
王建葦
時間:
2022-4-2 12:01
此帖僅作者可見
作者:
董宸佑
時間:
2022-4-9 11:54
此帖僅作者可見
作者:
林羿丞
時間:
2022-4-9 11:56
此帖僅作者可見
作者:
李穎俊
時間:
2022-4-9 11:57
此帖僅作者可見
作者:
曾宥程
時間:
2022-4-9 11:57
此帖僅作者可見
作者:
黃柏叡
時間:
2022-4-9 11:57
此帖僅作者可見
作者:
王銘鴻
時間:
2022-4-9 12:00
此帖僅作者可見
作者:
陳羿安
時間:
2022-4-9 12:01
此帖僅作者可見
作者:
郭哲維
時間:
2022-4-16 11:30
此帖僅作者可見
作者:
張淯祺
時間:
2022-4-16 11:38
此帖僅作者可見
作者:
林羿丞
時間:
2022-4-16 11:41
此帖僅作者可見
作者:
李穎俊
時間:
2022-4-16 11:41
此帖僅作者可見
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2
