一、拓扑排序

1.简介

拓扑排序的英文名是 Topological sorting。拓扑排序要解决的问题是给一个图的所有节点排序，目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

在一个$DAG$（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边$(u,v)$， 都可以有 $u$ 在 $v$ 的前面。若给定一个$DAG$，如果从 $i$ 到 $j$ 有边，则认为 $j$ 依赖于 $i$ 。如果 $i$ 到 $j$ 有路径，则称 $i$ 间接依赖于 $j$ 。

若是有环图，则不存在拓扑排序。

2. 求解拓扑排序

• 从图中选择一个入度为零的点。
• 输出该顶点，从图中删除此顶点及其所有的出边。
• 重复上面两步，直到所有顶点都输出，拓扑排序完成。
• 若图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

为了完成这个程序，我们还需要利用 $STL$ 库中的队列，同时我们也要注意在拓扑排序中所应用的 $BFS$ 的思想。

3.核心代码

void topu()
{queue<ll> q;for(ll i=1;i<=n;i++)if(du[i]==0)q.push(i);while(!q.empty()){ll u=q.front();q.pop();cout<<u<<" ";for(ll i=p[u];i!=-1;i=e[i].next){ll v=e[i].v;du[v]--;if(du[v]==0)q.push(v);}}
}

时间复杂度为$O(V+E)$

二、欧拉图

1.概念

• 欧拉回路：通过图中每条边恰好一次的回路。
• 欧拉路径：通过图中每条边恰好一次的路径。
• 欧拉图：具有欧拉回路的图。
• 半欧拉图：具有欧拉通路但不具有欧拉回路的图。

2.性质

（1）无向图

• 若一个无向图 $G$ 存在欧拉路径，当且仅当 $G$ 恰有 $0$ 或 $2$ 个奇度顶点

• 若一个无向图 $G$ 存在欧拉回路，当且仅当 $G$ 不存在奇度顶点且连通

• 若一个无向图 $G$ 是包含两个奇度顶点的连通图时， $G$ 的欧拉路径必定以这两个点为端点

（2）有向图

• 若一个有向图 $G$ 存在欧拉路径，当且仅当 $G$ 是弱连通（将有向边看作无向边后连通）有向图，且满足以下两个条件之一：

  • 所有顶点的入度和出度相同
  • 有一个顶点相差 $1$，有一个顶点相差 $-1$，其他顶点的入度和出度相同

• 若一个有向图 $G$ 存在欧拉回路，当且仅当 $G$ 是强连通有向图且所有顶点的入度和出度相同

• 若一个有向图 $G$ 包含两个入度和出度不相同的顶点且有欧拉路径时， $G$ 的欧拉路径必定以这两个点为端点

3.求出欧拉路径

（1）无向图

计算无向图的欧拉路经可以用“套圈法”、基于深度优先搜索来实现。 从一个合适的顶点出发进行深度优先搜索。当搜到一个顶点 $u$ 时：

1. 如果此时没有顶点与该顶点相连，那么就将 $u$ 加入路径中并回溯
2. 如果有顶点 $v$ 与顶点 $u$ 相连，那么就删除无向边$<u,v>$，并继续搜索顶点 $v$ 。将所有和 $u$ 相邻的顶点遍历完之后，将 $u$ 加入路径中。

void dfs(ll u)
{if(du[u]>0){for(ll v=1;v<=n;v++){if(mp[u][v]){mp[u][v]--;mp[v][u]--;du[u]--;dfs(v);}}}ans[++cnt]=u;
}

（2）有向图

方法完全一致，这里可以对链式前向星做一定的优化。

void dfs(ll u)
{for(ll i=p[u];i!=-1;i=p[u]){ll v=e[i].v;p[u]=e[i].next;if(vis[i])continue;vis[i]=true;dfs(v);}ans[++cnt]=u;
}

三、作业

1.拓扑

B3644 【模板】拓扑排序 / 家谱树

P4017 最大食物链计数

P4089 [USACO17DEC]The Bovine Shuffle S

2.欧拉图

P1341 无序字母对

P2731 [USACO3.3]骑马修栅栏 Riding the Fences

P7771 【模板】欧拉路径