Code Đường đi Euler – Euler paths

Nguồn đề bài: http://www.spoj.com/KSTN/problems/EULER/

1. Đề bài Đường đi Euler

Một đường đi trong đồ thị G=(X,E) được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình Euler. Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm 1837.

Bài toán:

Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm 1 đường đi Euler trên G.

Input

Dòng 1: Chứa hai số n, m .

M dòng tiếp theo: Dòng thứ i có dạng hai số nguyên u, v. Trong đó u, v là chỉ số hai đỉnh đầu mút của cạnh thứ i.

Output

Gồm 1 dòng duy nhất là 1 dãy các số mô tả các đỉnh trên đường đi Euler

Ví dụ

Input:
8 9
1 2
1 3
4 2
4 3
4 5
4 6
5 7
6 8
7 8

Output:
1 2 4 5 7 8 6 4 3 1

Giới hạn:
1 <= n <= 100
1 <= m <=n(n-1)/2

Áp dụng thuật toán euler để làm bài này.

code tham khảo thuật toán euler

a. Code pascal

b. Code C++

 

Code Đường đi Euler – Euler paths, duong di euler pascal, c++, thuật toán euler, chuyen de euler,Euler paths

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *