USACO 2019 US Open Contest, Bronze Problem 2 Milk Factory
The milk business is booming! Farmer John's milk processing factory consists of?NN?processing stations, conveniently numbered?1…N1…N?(1≤N≤1001≤N≤100), and?N?1N?1?walkways, each connecting some pair of stations. (Walkways are expensive, so Farmer John has elected to use the minimum number of walkways so that one can eventually reach any station starting from any other station).
To try and improve efficiency, Farmer John installs a conveyor belt in each of its walkways. Unfortunately, he realizes too late that each conveyor belt only moves one way, so now travel along each walkway is only possible in a single direction! Now, it is no longer the case that one can travel from any station to any other station.
However, Farmer John thinks that all may not be lost, so long?as?there is at least one station?ii?such that one can eventually travel to station?ii?from every other station. Note that traveling to station?ii?from another arbitrary station?jj?may involve traveling through intermediate stations between?ii?and?jj. Please help Farmer John figure out if such a station?ii?exists.
INPUT FORMAT (file factory.in):
The first line contains an integer?NN, the number of processing stations. Each of the next?N?1N?1?lines contains two space-separated integers?aiai?and?bibi?with?1≤ai,bi≤N1≤ai,bi≤N?and?ai≠biai≠bi. This indicates that there is a conveyor belt that moves from station?aiai?to station?bibi, allowing travel only in the direction from?aiai?to?bibi.
OUTPUT FORMAT (file factory.out):
If there exists a station?ii?such that one can walk to station?ii?from any other station, then output the minimal such?ii. Otherwise, output??1?1.
SAMPLE INPUT:
3
1 2
3 2
SAMPLE OUTPUT:
2
Problem credits: Dhruv Rohatgi
中文版
牛奶生意正紅紅火火！Farmer John的牛奶加工廠內有NN個加工站，編號為1…N1…N（1≤N≤1001≤N≤100），以及N?1N?1條通道，每條連接某兩個加工站。（通道建設很昂貴，所以Farmer John選擇使用了最小數量的通道，使得從每個加工站出發都可以到達所有其他加工站）。
為了創新和提升效率，Farmer John在每條通道上安裝了傳送帶。不幸的是，當他意識到傳送帶是單向的已經太晚了，現在每條通道只能沿著一個方向通行了！所以現在的情況不再是從每個加工站出發都能夠到達其他加工站了。
然而，Farmer John認為事情可能還不算完全失敗，只要至少還存在一個加工站ii滿足從其他每個加工站出發都可以到達加工站ii。注意從其他任意一個加工站jj前往加工站ii可能會經過ii和jj之間的一些中間站點。請幫助Farmer John求出是否存在這樣的加工站ii。
輸入格式（文件名：factory.in）：
輸入的第一行包含一個整數NN，為加工站的數量。以下N?1N?1行每行包含兩個空格分隔的整數aiai和bibi，滿足1≤ai,bi≤N1≤ai,bi≤N以及ai≠biai≠bi。這表示有一條從加工站aiai向加工站bibi移動的傳送帶，僅允許沿從aiai到bibi的方向移動。
輸出格式（文件名：factory.out）：
如果存在加工站ii滿足可以從任意其他加工站出發都可以到達加工站ii，輸出最小的滿足條件的ii。否則，輸出?1?1。
輸出樣例：
3
1 2
3 2
輸出樣例：
2
供題：Dhruv Rohatgi
計算機
翰林USACO課程體系流程圖
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
