[Pascal] Tìm chu trình Euler | Nguyễn Hoàng Huy

Đề bài: Cho một đồ thị có n đỉnh và các cạnh nối. Tìm một chu trình Euler bắt đầu từ đỉnh 1 (đảm bảo đồ thị nhập vào có một chu trình Euler).
Input: có dạng như sau:

• Dòng đầu chứa số đỉnh n và số m.
• m dòng tiếp theo chứa 3 số nguyên u, v, k. Thể hiện giữa đỉnh u và đỉnh v có k cạnh nối.

Output: in ra một chu trình Euler tìm được, các đỉnh cách nhau bởi một dấu cách.
Ví dụ:

Input	Output
3 3	1 2 1 3 2 3 1
1 2 2
2 3 2
3 1 2

Giải

Thuật toán để tìm chu trình Euler như sau:

Tạo mảng P để ghi đường đi và ngăn xếp S chứa các đỉnh để xét.

B1: Xếp vào S một đỉnh đầu tiên sẽ xét (ở đây là đỉnh 1)

B2: Xét đỉnh trên cùng của ngăn xếp S, giả sử đỉnh đó là u:

• Nếu u là đỉnh cô lập thì lấy u ra khỏi ngăn xếp và thêm u vào P.
• Nếu u kề với v (v là đỉnh đầu tiên trong tập đỉnh kề với u) thì đẩy v vào ngăn xếp, sau đó xóa bỏ số cạnh giữa u và v đi 1 đơn vị.

B3: Quay lại bước 2 cho tới khi ngăn xếp rỗng. Kết quả là chu trình Euler trong P theo thứ tự ngược lại.

Chương trình:

Xem tại đây: http://mivi.pro/lrWk1AH

Bài viết có tham khảo từ:
http://simplecodecjava.blogspot.com/2015/09/thuat-toan-tim-uong-i-va-chu-trinh-euler.html