欧拉路

欧拉跑过的七桥古塘，让你，心驰神往……

一 引入

1 欧拉路问题

数学家欧拉在研究著名的德国哥尼斯堡(Koenigsberg)七桥问题时，发现欧拉路。流经哥尼斯堡的普雷格尔河中有两个岛，两个岛与两岸共4处陆地通过7座桥彼此相联。七桥问题就是如何能从任一处陆地出发，经过且经过每个桥一次后回到原出发点。

欧拉由此提出了著名的欧拉定理。

欧拉路问题，也称“一笔画问题”。即给定一张图（有向或无向），求出图上的一条路径，使得这条路径经过图上的所有边恰好一次。

若存在满足上述条件的道路，则这条道路被称为欧拉道路。
若一条欧拉道路的起点与终点相重合，则这条道路被称为欧拉回路。若图中已判定存在欧拉回路，则从任意一点出发，均可以回到该点。

2 解的存在性

存在一条欧拉道路，首先需要保证图是联通的。

对于一个联通图，定义$d_i$为节点$i$所连接的边数（也就是度）。对于图上$d_i$的值为奇数的节点，称之为奇点。
定理：（蒟蒻并不会证明）

1. 若图上没有奇点，则一定存在欧拉回路。
2. 若图上存在两个奇点，则一定存在欧拉道路，且该道路以这两个奇点为端点。
3. 若图上存在多于两个奇点，则不存在欧拉道路。

---

二 实现

算法的思路很简单：
先判断解的有无，然后从奇点（若不存在就从任意一点）出发，搜索整张图，并把每次走过的边删除。那么我们访问节点的先后顺序就是欧拉道路。

有一点需要注意，当使用边表存图时，删边需要把正反两条边同时删除。故边从$1$开始标号，使得$i \text{xor} 1$总是$i$的反向边。

给出代码：

const int CP=1e3+3;
const int CE=CP*CP;

const int INF=0x3f3f3f3f;

//边表
class fs{
  public:
    int to,nxt;
}E[CE];
int hd[CP],ecnt=1; //边的标号从1开始
void add(int x,int y){
    E[++ecnt].to=y;
    E[ecnt].nxt=hd[x];
    hd[x]=ecnt;
}

//variable define
int n,m;
int d[CP]; //度

//判断解的存在
bool examine()
{
    int sum=0;
    for(int i=1;i<=n;i++)
        if(d[i]%2)
            sum++;
    return (!sum) || (sum==2);
}

//求解
bool vis[CE]; //每条边是否访问过
int list[CP]; //保存答案
void dfs(int u)
{
    for(int k=hd[u]; k; k=E[k].nxt)
        if(!vis[k])
        {
            vis[k]=vis[k^1]=true; //正反边同时标记
            dfs(E[k].to);
        }
    list[++list[0]]=u; //记录，注意要倒序输出，因为是在回溯时记录
}
bool solve()
{
    if(!examine())
        return false;
    int st=1; //起点默认为1
    for(int i=1;i<=n;i++)
        if(d[i]%2) //为奇点
            st=i; //从奇点出发
    dfs(st);
    return list[0]==n; //当list[0]!=n时，可以判定图不联通
}