---
# System prepended metadata

title: D - Unicyclic Components 2(400)
tags: [Atocder]

---

# 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)