---
# System prepended metadata

title: Eulerian Cycle

---

# Eulerian Cycle

歐拉迴路

每個頂點都是偶數邊(自己走到自己不算),且每個點都要能走到每個點,因此任兩個點的邊數都是2(來回),開一個cnt紀錄當前節點走到哪一個其他節點了,把每一個節點都走過一遍後,此迴路就是歐拉迴路,注意是遞迴完的時候才紀錄,也就是backtracking

```cpp=
void dfs(int now) {
    while (nxt[now] < k) {  //還有沒有沒走到的節點
        int go = nxt[now]++;  //下一個要去的結點
        dfs(go);
        path.push_back(go);  //遞迴完才紀錄路徑
    }
}
```
```
a d d c c d b c b b d a c a b a 
```
![](https://i.imgur.com/2C7UqXD.png)
