切換
舊版
前往
大廳
主題

ZeroJudge - a290: 新手訓練系列 ~ 圖論 解題心得

Not In My Back Yard | 2019-05-18 22:54:51 | 巴幣 0 | 人氣 342

題目連結:


題目大意:
第一列給定兩正整數 N 、 M (N ≦ 800 , M ≦ 1, 000, 000),代表有 N 座城市,且接下來有 M 列輸入,分別代表城市與城市之間的連通情形(單向)。

接著的 M 列輸入,每列給定兩正整數 a 、 b (1 ≦ a 、 b ≦ N),代表城市 a 可以通到城市 b (反過來不行)。

再來一列輸入也同樣給定兩正整數 A 、 B (1 ≦ A 、 B ≦ N)。試問城市 A 可否走到城市 B 。可以的話輸出「Yes!!!」;反之,輸出「No!!!」。



範例輸入:
8 32
7 4
2 5
7 5
3 7
2 1
2 2
2 4
4 4
4 7
8 5
7 5
5 2
6 7
7 5
8 8
4 7
6 3
4 1
4 4
8 7
3 4
2 6
6 1
6 8
4 5
7 5
6 6
4 4
2 6
5 3
7 4
1 3
1 3


範例輸出:
Yes!!!


解題思維:
直接從城市 A 開始用廣度優先搜尋法(BFS)下去跑,連結到的城市,如果沒被加入過佇列的話就加入佇列(Queue)裡,等等再探訪。

當把城市 B 加入佇列裡即可跳出迴圈,代表城市 A 可連到城市 B 。反之,從頭到尾城市B都沒被加入到佇列裡,代表城市 A 無法通到城市 B

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

創作回應

更多創作