g554: 周遊列國(Travel)
Tags :
Accepted rate : 18人/30人 ( 60% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-01 21:45

Content

伊蕾娜十分喜歡短篇小說集《妮可冒險記》,同時也很崇拜書中的主角妮可, 從小就立志成為魔女,希望未來能夠像妮可一樣周遊列國、四處旅行。在伊蕾娜 正式成為魔女之後,決定開始她的漫長旅行,與世上形形色色的人們邂逅,編織 出相逢與離別的故事。

然而,伊蕾娜在正式踏上旅行之前,她注意到任意兩個國家之間不一定存 在道路直接相連,甚至即使相連也只能單向通行。於是伊蕾娜開始思考,是否 存在一條路線,讓她能順利拜訪世界上所有的國家(此路線允許經過她曾拜訪 過的國家)。

Input

第一行輸入兩個非負整數 N (1 ≤ N ≤ 100000 )、M (0 ≤ M ≤ 1000000 ),分別表示國家的 數量以及連接道路的數量;其中國家的編號為 1 ~ N。 接下來的 M 行,每行有兩個正整數 Ai、Bi (1 ≤ Ai , Bi ≤ N 且 Ai ≠ Bi ),代表存 在一條單向的道路從國家 Ai抵達國家 Bi;可能存在不只一條從國家 Ai 抵達國家 Bi的道路。

Output

輸出僅包含一個字串;假設伊蕾娜最初所在的國家編號為 1(且國家 1 在伊 蕾娜出發前即視為已拜訪),若存在一種走訪路線(無論途中是否有再度走訪已 經拜訪過的國家),使得伊蕾娜能夠拜訪其餘所有國家則輸出 Yes,反之則輸出 No。

Sample Input #1
3 4
1 2
2 1
1 3
3 1
Sample Output #1
Yes
Sample Input #2
4 4
1 2
1 3
2 4
3 4
Sample Output #2
No
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (5%): 1.0s , <10M
不公開 測資點#1 (5%): 1.0s , <10M
不公開 測資點#2 (5%): 1.0s , <50M
不公開 測資點#3 (5%): 1.0s , <50M
不公開 測資點#4 (5%): 1.0s , <50M
不公開 測資點#5 (5%): 1.0s , <50M
不公開 測資點#6 (5%): 1.0s , <50M
不公開 測資點#7 (5%): 1.0s , <50M
不公開 測資點#8 (5%): 1.0s , <50M
不公開 測資點#9 (5%): 1.0s , <50M
不公開 測資點#10 (5%): 1.0s , <50M
不公開 測資點#11 (5%): 1.0s , <50M
不公開 測資點#12 (5%): 1.0s , <50M
不公開 測資點#13 (5%): 1.0s , <50M
不公開 測資點#14 (5%): 1.0s , <1K
不公開 測資點#15 (5%): 1.0s , <50M
不公開 測資點#16 (5%): 1.0s , <50M
不公開 測資點#17 (5%): 1.0s , <10M
不公開 測資點#18 (5%): 1.0s , <1K
不公開 測資點#19 (5%): 1.0s , <1K
Hint :

範例 1 說明: 存在以下走訪路線: 1 → 2 → 1 → 3 伊蕾娜能夠拜訪所有國家,故輸出 Yes。

範例 2 說明: 不存在一種走訪路線使得伊蕾娜能夠拜訪所有國家,故輸出 No。

11/01 21:45 因看到有人過假解,故更新測資(並未rejudge)

Tags:
出處:
TOI練習賽202110潛力組 [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
27947
r1cky (木叢欉木叢)
g554
68 2021-11-06 20:32
27823
fire5386 (fffelix)
g554
想法
248 2021-10-31 15:08