• 题目来源

  id=2230">http://poj.org/problem?id=2230

• 题目大意
  
  求无向图从起点1開始从不同方向经过全部边的一条路径。输出随意一条。

• 题解
  
  把无向图的边拆成两条方向相反的有向边，做欧拉回路。
  
  欧拉回路做法：
  
  1、起点入栈。（回路的话起点能够是随意的）
  
  2、扫描与起点相连的全部未被标记的边，对每条这种边都标记它，然后它的终点入栈，递归处理；
  
  3、假设从某个结点出发没有未被标记的边，则把这个结点出栈，增加答案序列中；
  
  4、反复以上步骤，直到栈空。
  
  5、对无向图，倒序的答案序列是一条欧拉回路。有向图正序倒序均可。

• Code

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 10005, maxm = 100010, nil = 0;

int n, m;

int e, pnt[maxn], nxt[maxm], u[maxm], v[maxm];

bool f[maxm];

void add(int a, int b)

{

    u[++e] = a; v[e] = b;

    nxt[e] = pnt[a]; pnt[a] = e;

}

void init()

{

    int a, b;

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++i)

    {

        scanf("%d%d", &a, &b);

        add(a, b);

        add(b, a);

    }

}

void dfs(int k)

{

    for(int j = pnt[k]; j != nil; j = nxt[j])

    {

        if(!f[j])

        {

            f[j] = true;

            dfs(v[j]);

        }

    }

    printf("%d\n", k);

}

void work()

{

    dfs(1);

}

int main()

{

    init();

    work();

    return 0;

}