Code Đường đi Euler - Euler Paths - Kiến Thức 24h

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

const fi=''; nmax=100; type data=longint; var f:text; A:array[1..nmax,1..nmax] of byte; n,m:data; Dem:array[1..nmax] of data; H:array[0..5000] of data; sta:data; res:ansistring; procedure docfile; var i,j,u,v:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to n do begin dem[i]:=0; for j:=1 to n do a[i,j]:=0; end; for i:=1 to m do begin readln(f,u,v); a[u,v]:=1; a[v,u]:=1; inc(dem[u]); inc(dem[v]); end; close(f); end; procedure them(s:data); begin inc(sta); h[sta]:=s; end; function xem:data; begin exit(h[sta]); end; function layra:data; begin layra:=h[sta]; dec(sta); end; procedure euler; var i,j,s,x:data; st:string; begin sta:=0; x:=1; for s:=1 to n do if odd(dem[s]) then begin x:=s; break; end; them(x); res:=''; while sta>0 do begin j:=xem; for i:=1 to n do if (a[i,j]=1) then begin them(i); a[i,j]:=0; a[j,i]:=0; break; end; if j=xem then begin //write(j,' '); str(j,st); res:=st+' '+res; dec(sta); end; end; writeln(res); end; begin docfile; euler; end.

b. Code C++

#include <iostream> #include <fstream> #include <cmath> #include <cstring> #include <cstdlib> #include <ctime> #include <algorithm> #include <queue> #include <set> #include <vector> #include <map> #include <sstream> #define pb push_back #define mp make_pair #define ll long long #define ull unsigned long long using namespace std; const int nm=102; int n,m,a[nm][nm]; int ns,st[nm*nm]; int bac[nm]; void nhap() { scanf("%d%d",&n,&m); int i,u,v; for(i=1;i<=m;++i) { scanf("%d%d",&u,&v); a[u][v]=a[v][u]=1; bac[u]++;bac[v]++; } } void xuli() { int i,j; for(i=1;i<=n;++i) if (bac[i]%2) break; ns=1; if (i<=n) st[1]=i;else st[1]=1; while (ns) { i=st[ns]; for(j=1;j<=n;++j) { if (a[i][j]) { st[++ns]=j;a[i][j]--;a[j][i]--; break; } } if (i==st[ns]) { printf("%d ",i);ns--; } } } int main() { //freopen("5.in","r",stdin); //freopen("vd.out","w",stdout); nhap();xuli(); }

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