# D - Unicyclic Components 2(400) ###### tags: `Atocder` ## Question [D - Unicyclic Components 2](https://atcoder.jp/contests/abc292/tasks/abc292_d) ## Idea 1 (wrong) 1. 將連線的紀錄存在數字較小的那一方， vector也只由紀錄較小的那一方存取。 2. 這樣當在做dfs的時候，就能夠從最小的數字開始一路找尋下去。 3. 但問題出在，當兩條邊的連接點的數字最大，就會導致dfs無法直接尋訪全部的路線。 ![](https://i.imgur.com/YQSwnnS.png) 連線的紀錄會存在5跟7(9最大)，導致跑dfs的時候，即便跑到9也沒辦法透過9繼續往下跑，因為9根本沒有儲存5、7的連線紀錄。 [wrong code](https://atcoder.jp/contests/abc292/submissions/39985022) ## Idea 2 (correct) 1. 在記錄連線的時候，兩個點都要做紀錄。 2. 因為兩個點都有紀錄，所以跑dfs做邊的計算時，每條邊會被算到兩次。 3. 尋訪結束後，先將邊的數量/2，然後再跟點的數量做比對。 [correct code](https://atcoder.jp/contests/abc292/submissions/40143658)