#25611: 樹 vs 圖


s0254020@gm.ncue.edu.tw (鄭常仁)

學校 : 不指定學校
編號 : 155289
來源 : [220.133.172.118]
最後登入時間 :
2021-06-07 10:25:58
b967. 4. 血緣關係 -- 2016年3月apcs | From: [220.133.172.118] | 發表日期 : 2021-06-06 19:08

以樹下去做:

1.找出祖先

1.1.建立檢測表

1.2紀錄誰為小孩,測資一:關係0 1,1為小孩、關係0 2,2為小孩。

1.2掃描檢測表會發現有一個人不曾是小孩。

1.3不曾是小孩的即為祖先

2.以祖先做DFS或BFS找出最大深度與最大深度者。EX:最大深度3,最大深度者為4

3.修改關係表,從祖先到最大深度者之間的關係調換,7->0->1->4改為4->1->0->7

4.以修改過的樹,祖先為4下去做DFS或BFS,找出最大深度。

以圖下去做:

1.建立雙向關係。EX: 0跟1 2 3 7有關係、1跟4、5、0有關係

2.隨便找一個點做DFS或BFS找出最遠距離與最遠距離度者。EX:以0做DFS找出4最遠(或6)

(由於是雙向關係要避免loop,EX:0找1 1找0 0找1 1找0)

3.以找出的點再做一次DFS或BFS。EX:以0做DFS找出4最遠,以4做DFS找出最遠為6,距離為4

 

 
ZeroJudge Forum