切換
舊版
前往
大廳
主題

ZeroJudge - c131: 00615 - Is It A Tree? 解題心得

Not In My Back Yard | 2020-09-25 00:00:14 | 巴幣 2 | 人氣 253

題目連結:


題目大意:

但是每筆測試資料不給定邊的個數,而且每筆測資可能佔不定量列。每筆有不定量對的 (i, j) ,代表有一條有向邊從 i 到 j。當給定一組 (0, 0) 時,代表該筆測試資料結束。而當有一筆測資只有給定一對 (-1, -1) 時,代表輸入結束。

跟昨天的題目一樣,試問給定的圖是否為一棵樹?輸出格式參見範例輸出。

注:本題的樹可以為空,見範例輸出 Case 4 的對應輸入。



範例輸入:
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

0 0
1 2 0 0
1 2 1 3 4 5 0 0
1 1 0 0
1 2 2 1 0 0
1 2 1 2 0 0

1 2 2 3 3 1 4 5 0 0

-1 -1


範例輸出:
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.
Case 4 is a tree.
Case 5 is a tree.
Case 6 is not a tree.
Case 7 is not a tree.
Case 8 is not a tree.
Case 9 is not a tree.
Case 10 is not a tree.


解題思維:
作法也跟昨天的題目差不多,但是這次要額外紀錄邊的個數。然後按照昨天的作法去判斷。但是要注意本題的樹可以是空的,也就是沒有任何的節點與邊存在。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作