欧拉回路总结

一、存在条件

一个无向图存在欧拉路当且仅当该图是连通的且有且只有2个点的度数是奇数，此时这两个点只能作为欧拉路径的起点和终点。

相关题目：http://hihocoder.com/problemset/problem/1176

二、求欧拉路径（Fleury算法）

核心思想是：从奇数点开始走，每次走一条没走过的边，直到不能走为止。若存在欧拉路径，则路径一定为一条欧拉路径。

实现：利用DFS遍历，模仿堆栈的过程。需要注意的是最后一步Path[ PathSize ] ← u，不能放到函数的开始（此处没有仔细思考过，先Mark一下）。最后，数组Path为欧拉路径的逆向。

DFS(u):
    While (u存在未被删除的边e(u,v))
        删除边e(u,v)
        DFS(v)
    End
    PathSize ← PathSize + 1
    Path[ PathSize ] ← u

相关题目：http://hihocoder.com/problemset/problem/1181

三、拓展

在某些条件下，哈密顿回路的问题能够转化成欧拉路径的问题来解决。

相关题目：http://hihocoder.com/contest/hiho51/problem/1

相关代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;

int N;

typedef struct Node{
    int id;
    vector<int> b;
    int i;
    Node(int id) :id(id), i(0){};
    void add(int a){ b.push_back(a); };
    int get()
    {
        if (i < b.size())
        {
            i++;
            return b[i - 1];
        }
        return -1;
    }
};

vector<Node*> node;

void dfs(int i, bool is)
{
    int next = node[i]->get();;
    while (next != -1)
    {
        dfs(next, false);
        next = node[i]->get();
    }
    if(!is) cout << i % 2  ;
}


int main()
{
    //freopen("t.txt", "r", stdin);
    int n;
    cin >> n;

    if (n == 1)
    {
        cout << 0 << 1 << endl;
        return 0;
    }


    int N = pow(2, n - 1) - 1, M = N + 1;

    for (int i = 0; i <= N; i++)
        node.push_back(new Node(i));

    for (int i = 0; i <= N; i++)
    {
        int to1 = (i << 1) % M, to2 = to1 + 1;

        node[to1]->add(i);
        node[to2]->add(i);
    }

    for (int i = 1; i <= N; i++)
    {
        if (node[i]->b.size() % 2 || i == N)
        {
            dfs(i, true);
            break;
        }
    }

    return 0;
}