題目連結:
題目大意:
但是每筆測試資料不給定邊的個數,而且每筆測資可能佔不定量列。每筆有不定量對的 (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.
解題思維:
作法也跟昨天的題目差不多,但是這次要額外紀錄邊的個數。然後按照昨天的作法去判斷。但是要注意本題的樹可以是空的,也就是沒有任何的節點與邊存在。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。