图论这……感觉是知识点多，算法多，但用的频率不一定高，容易忘记，这里就整点板子防老年痴呆
欧拉路径
即一笔画问题，定义为：
图中经过所有边恰好一次的路径叫欧拉路径。如果此路径的起点和终点相同，则称其为一条欧拉回路。
注意图必须连通，可用并查集或dfs判断
关于判断欧拉路径是否存在：
以下 \(S\) 为起点， \(T\) 为终点，并保证唯一
- 有向图欧拉路径：\(S\) : 入度 + 1 = 出度； \(T\) : 入度 = 出度 + 1； 其余节点： 入度 = 出度
- 有向图欧拉回路：所有节点： 入度 = 出度
- 无向图欧拉路径：\(S, T\) ： 度数为奇； 其余节点： 度数为偶
- 无向图欧拉回路：所有节点： 度数为偶
在欧拉回路中，起点终点可以为任意点
关于求出欧拉回路
欧拉回路与欧拉路径（上）
欧拉回路与欧拉路径（下）
有向图：
从 \(S\) 开始跑dfs，每条边跑完后删去（打上标记），跑完所有儿子后再将该点入栈。
最后将整个栈反过来即为答案
关于正确性可画图感性理解
我是懒狗我不管
参考代码：
//N 为点的数量， M 为边的数量
int head[N], tot;
struct edge{
int to, nxt;
bool vis;
}e[M];
//有向边
int ans[M], cnt;
//每条边一次，共 M + 1 个点
//注意 M 开为数据范围 +5 即可
inline void Dfs(int now){
for(int i = head[now]; i; i = e[i].nxt){
if(!e[i].vis){
//未访问过
e[i].vis = 1;
Dfs(e[i].to);
//访问
}
}
ans[++ cnt] = now;
//入答案栈
}
一定注意最后答案是倒着入的栈，故需倒序输出
发现若用链式前向星存图，我们找未访问过的边时需将与该点相连的所有边都访问一次。
在这一操作上，其实使用领接链表更为便捷，以下为代码。
int num[N];//用法具体看Dfs函数
vector<int> to[N];
int ans[M], cnt;
inline void Dfs(int now){
for(int i = num[now]; i < to[now].size(); i = num[now]){
//以访问过的节点再也不会被访问啦
num[now] ++;
Dfs(to[now][i]);
}
ans[++ cnt] = now;
}
其实链式前向星应该也是支持这个操作的。只是
我是懒狗我不管
下面会提到如何实现
无向图：
类似于有向图的方法，只是删边时正边和反边一起删除罢了。
此时，若使用领接链表，会发现并不好处理删边，我们转回链式前向星。
实际上我们只是在找边时将查询的起始位置更新了，来避免多余的查询，将这思想放在链式前向星上，便是以下的代码。
int head[N], tot = 1;
//tot 从奇数开始方便查询反边
struct edge{
int to, nxt;
bool vis;
//因为有未访问但被删除的反边存在，我们还是需要删除标记
}e[M << 1];
//无向图
int ans[M], cnt;
inline void Dfs(int now){
for(int i = head[now]; i; i = head[now]){
if(e[i].vis){
//边已被删
head[now] = e[i].nxt;
continue;
}
e[i].vis = 1;
e[i ^ 1].vis = 1;
//删边
head[now] = e[i].nxt;
Dfs(e[i].to);
ans[++ cnt] = now;
//此句放循环外或内还并不清楚，有知道的麻烦留言提醒，谢谢了
}
}