# Review đường đi - chu trình Euler - cycle 1

[Original post](https://hackmd.io/@thangb/BJ1jSU1rY)

- Plus: cover khá chi tiết được định lý và chứng minh các định lý, cộng thêm triển khai cơ bản cho thuật toán tìm chu trình Euler.
- Minus: còn mắc nhiều lỗi diễn đạt. Phần code còn nhiều chỗ chưa ổn và vẫn còn dùng _magic_.

## Review chi tiết
### Mở đầu
Nên mở đầu chi tiết hơn, và cố gắng đưa bài blog trở nên tổng quát chứ không nên đặt nó trong context lập trình thi đấu, vì chủ đề này cũng là một chủ đề toán học và cũng có ý nghĩa trong thực tiễn.

### Định nghĩa
- Nên nói thêm rằng chu trình Euler là 1 đường đi Euler.
- Nên định nghĩa thêm "Đồ thị Euler" (Eulerian graph), tức đồ thị có đường đi Euler. Với định nghĩa này có thể rút gọn một số chỗ phía sau.

### Nguồn gốc.
Phần này nên đưa lên trên, có thể gộp với phần mở đầu để tạo hứng thú cho người đọc.

### Dấu hiện nhận biết tồn tại đường đi và chu trình Euler
- Về tiêu đề nên thêm "Định lý" vào đằng trước để khẳng định độ đúng đắn của nó.
#### Định lý 1
- Về phát biểu không nên liệu kê các ý sau "với mọi đỉnh", bởi vì ý thứ 2 không liên quan lắm. Thay vào đó nên để các ý thành:
- Mọi đỉnh có số bậc ra bằng số bậc vào.
- Tất cả các đỉnh, ....
- Nhân tiện thì ý thứ 2 trong bài như hôm trước mình nói là **chưa đúng**. Đồ thị có thể có nhiều thành phần liên thông, nhưng 1 thành phần liên thông là **phải chứa tát cả các cạnh trong đồ thị**, và các thành phần liên thông còn lại không có cạnh nào (tức chứa duy nhất 1 đỉnh và không có khuyên).
- Khi sửa lại ta cũng phải đề cập lại 1 lần nữa phần này sau chứng minh, do chính bản thân mình cũng nhầm, và cũng đưa ra các ví dụ cho các bạn hiểu.
##### Chứng minh chiều đảo
- Typo trong bổ đề: "...một cạnh ra chưa thăm từ $u$ **đề** đi."
- Về diễn đạt:
- Trong bổ đề, "Với mỗi đỉnh $v \ne u$...": nên nói rằng "Trong quá trình đi, trong khi mà ta gặp 1 đỉnh $v$ chưa phải là $u$ ..."
- "Xóa hết các cạnh trên $C$": xóa hết các cạnh của chu trình C trong G đi.
- "... các đồ thị con không liên thông ...": với cách diễn đạt như thế này là ngược đọc lại sẽ nghĩ là G1 là đồ thị không liên thông, G2 là đồ thị không liên thông, ... Nếu như đã liệt kê đồ thị như thế này rồi mình nghĩ có thể đổi "không liên thông" thành "liên thông" để nói rõ là G1 là đồ thị liên thông, G2 là đồ thị liên thông, ...
- Vẫn thiếu case: nếu $C$ đã chứa hết toàn bộ cạnh của $G$, ta thu về chu trình Euler.

#### Định lý 2
- Vẫn là lưu ý về "liên thông cạnh" thay vì "liên thông đỉnh".
- Như mình nói ở đầu, chu trình euler cũng là 1 đường đi euler, vậy đoạn này cũng nên nói qua phần đó nữa.
- Thay vì nói là "nhiều nhất" thì có thể chia luôn ra 2 trường hợp:
- Mọi đỉnh có số bậc vào bằng ra (tức tồn tại chu trình euler).
- Có **chính xác** 1 đỉnh có số bậc vào nhiều hơn số bậc ra một đơn vị, và có **chính xác** 1 đỉnh khác có số bậc ra nhiều hơn số bậc vào 1 đơn vị.

#### Định lý 3
- Vẫn là lưu ý về "liên thông cạnh" thay vì "liên thông đỉnh".
- Vẫn giống như đò thị có hướng, thay vì nói là "xóa cạnh trên C" ta nên nói "xóa các cạnh của C trong G đi".

#### Định lý 4
- Vẫn là lưu ý về "liên thông cạnh" thay vì "liên thông đỉnh".

### Thuật toán tìm chu trình - đường đi Euler
- Cần đề cập rằng việc tìm chu trình và đường đi như đã đề cập ở phần chứng minh là dùng 1 thuật toán.

#### Thuật toán Hierholzer
Ta nên phát biểu thuật toán dưới dạng 1 thủ tục. Bước 1 thực tế không nằm trong thuật toán này, mà cho nó làm tham số, vì rõ ràng bước 5 là ta gọi thủ tực này với tham số khác.

Bước 1 nên tách ra làm 1 ý ở ngoài. Việc chọn đỉnh xuất phát là tùy thuộc vào loại đường đi mà ta muốn tìm.

Bước 2 và 3 nên nói là ta đang đi tìm chu trình $C$ ngay từ đầu. Cụm từ "mảng kết quả" cũng không được rõ nghĩa mình hiểu ở đây là $C$ nhưng người đọc có thể không hiểu.

Bước 5: ta không nói lặp lại bước 1. Ta cần nói là gọi lại thủ tục để tìm chu trình Euler xuất phát tại $u$.

Bước 6 cần nói nối D vào C tại đâu.

Ngoài ra phát biểu toán mới nói được là tìm duy nhất 1 chu trình D, trong khi đó ở chứng minh là ta nói rằng việc xóa $C$ sẽ tạo ra nhiều tplt chứ không phải chỉ 1.

Cũng cần nói thêm rằng tplt gồm có duy nhất 1 đỉnh thì cũng có chu trình Euler nhưng thủ tục sẽ trả vê danh sách cạnh rỗng, hoặc danh sách đỉnh gồm duy nhất đỉnh đó.

Bài chưa đề cập đến độ phức tạp của thuật toán. Cần nói ra điểm mạnh yếu của từng cấp trúc dữ liệu một: nếu ta dùng mảng/vector để lưu $C$ thì thuật toán sẽ là $O(m^2)$ vì việc cắt/nối danh sách sẽ diễn ra trong $O(m)$. Do đó ta mới sử dụng cấu trúc dữ liệu danh sách liên kết cho phép **chèn** 1 danh sách vào 1 vị trí đã biết trong $O(1)$.

##### Cài đặt mẫu.
- Ehm, thật ra cái cài đặt đó là cho đồ thị vô hướng :v. Với đồ thị có hướng ta không cần đánh dấu `used_edge` bởi vì nó không 2 chiều, các cạnh là unique rồi, nên `pop_back` xong là xóa luôn.
- Nên đề cập đến việc có triển khai khác sử dụng 2 stack thay vì 1 stack, tuy nhiên triển khai trong bài là dựa hoàn toàn vào chứng minh, và cũng rất dễ cài đặt.
- Việc **sử dụng `pop_back()` sẽ xóa danh sách kề trong đồ thị gốc**. Như vậy ta cần đề cập điều này trong bài và yêu cầu người sử dụng thuật toán copy đồ thị ra trước khi dùng. Hoặc có cách khác là duy trì $n$ con trỏ vào vị trí node đang duyệt hiện tại của danh sách kề cho từng đỉnh.
- Nên sử dụng `struct` cho cạnh. Ví dụ

struct Edge {
    int target, id;
};

hoặc ít nhất nói rằng first là target và second là id.
- Trong code có nhiều comment không cần thiếu, consider lược bỏ bớt nếu như dòng code đã self-explanatory.
- Ngược lại một số chỗ lại không giải thích, như tại sao ta lại có `while (adj[u].size())` (btw nên dùng `adj[u].empty()` thay thế), tại sao lại có `auto it = ++ans.begin()`, những chỗ này nó chưa tự giải thích.
- Nên giải thích thêm method `splice` của `std::list`, theo mình sẽ rất nhiều bạn không sử dụng list bao giờ, cần giải thích hoạt động của nó và link bài viết tương ứng từ cppreference.com đến.
- Nên tách `ans.push_back(u = v);` thành 2 câu lệnh để giảm bớt độ magic của code giúp các bạn mới học hiểu code dễ hơn.
- Nên cố gắng sử dụng tính năng của `C++11` (vì thi hsgQG sử dụng `C++11`). Trong bài có dùng structured binding là của `C++17` rồi.
- Syntax highlight của khối code nên là `cpp` hoặc `cpp=` thay vì `c++`.
- Cần nói đến những modification có thể cho code:
- Có thể trả về danh sách id cạnh thay vì danh sách id đỉnh. Với modification này là ta cần bỏ đi cái đoạn `t.pop_back()`.
- Again, với đồ thị có hướng ta không lưu ID cạnh trong danh sách kề.
- Có thể nói việc thêm `n` con trỏ vào đoạn này.
- Nên gọi thủ tục là `euler_walk` (mình sẽ giải thích ở ví dụ code mẫu dưới).

### Ứng dụng
#### CSES - Teleporters path
- Consider thêm mảng `out_deg` giúp các bạn tiện theo dõi.
- Không nên sử dụng nhiều magic quá ở chỗ kiểm tra, tức thay vì viết thế nên sử dụng `if else` truyền thống. Ngoài ra với `if else` có thể break sớm.
- Ta có thể **không cần nối n với 1** và việc gọi `euler_tour`/`euler_walk` vẫn đúng. Lý do là thay vì ban đầu thuật toán tìm chu trình bắt đầu từ 1 và quay về 1, nó sẽ vẫn đi từ 1 và nó dừng ở `n` luôn. Điều này thật ra sẽ rõ ràng hơn nếu ta _không dùng chứng minh chu trình Euler cho đường đi Euler_, tức bước đầu tiên là ta sẽ chứng minh là kiểu gì cũng có đường đi từ đỉnh xuất phát đến kết thúc, và xóa đi ta thu được các đồ thị Euler con.
- Riêng với bài này ta có thể không cần check `ok` mà việc kiểm tra `IMPOSSIBLE` chính là check xem `ans.size()` có bằng `m + 1` hay không luôn.
- Như suggest của mình ở trên, ta ko cần thêm cạnh ảo. Như vậy in kết quả trực tiếp từ đáp án được luôn.

#### VNOI Marathon 08 - Mê cung
Thay vì $u_0 u_1 u_2 \cdots u_{m - 1} u_0$ thì ta có thể cho đỉnh cuối là $u_m$ và bảo nó trùng với $u_0$. Như vậy ta không phải dùng phép $\bmod$. Ngoài ra là nói luôn $S_i$ là mảng tổng tiền tố của cost của các cạnh trên chu trình Euler tìm được.

## Suggest khác
- Nên thêm định nghĩa và kí hiệu về số bậc vào và ra (tức $deg(u), deg^-(u), deg^+(u)$), như vậy phát biểu và chứng minh có thể rút ngắn lại.
- Nên thêm hệ quả nhẹ: đồ thị có chu trình Euler thì ta luôn có thể bắt đầu và kết thúc chu trình bởi 1 đỉnh bất kì (tất nhiên là nếu nó có cạnh, xem lại lưu ý về "tính liên thông cạnh"). Hệ quả này cần nói lên đầu vì nó trong cả chứng minh tồn tại chu trình lẫn đường đi đều dùng.
- Thêm minh họa cho chứng minh: Như mình muốn ở đây là nên có 1 ví dụ kèm hình ảnh cho 1 chứng minh (vì các chứng minh còn là khá là tương tự). Vậy cần vẽ đồ thị ra, cần tìm 1 chu trình bất kì, và nói rằng các đồ thị con cũng có chu trình euler, và sau đó ta nối chúng vào như thế nào.
- Nên đổi tên các định lý thay vì đánh số định lý.
- Các định lý nên in đậm những điểm cần lưu ý.
- Thay vì nhóm định lý theo loại đồ thị (có hướng/vô hướng), có thể nhóm theo chu trình trước rồi đường đi sau, vậy việc "chứng minh tương tự" được đặt ở chứng minh mà nó muốn đề cập tới hơn.
- "Code mẫu" nên bỏ từ mẫu đi, có thể đặt là "Triển khai" hoặc cài đặt. Theo mình từ "mẫu" nó không tự nhiên.