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

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