02/10/2018, 14:31
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | 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();
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #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
