2022.6.4 集训：欧拉回路

posted on 2022-06-12 14:46:40 | under 学术 | source

2022.6.4 集训：欧拉回路

基本概念

定义

令 $G=(V,E)$ 为一个图。对于 $u\in V$，称 $u$ 的入度为 $d^+(u)$，出度为 $d^-(u)$，度为 $d(u)=d^+(u)+d-(u)$。

• 欧拉回路：在图 $G$ 中经过每条边一次并且仅一次的回路（$s=t$）。
• 欧拉路径：在图 $G$ 中经过每条边一次并且仅一次的路径。

判定

不考虑 $d(u)=0$ 的点，它们是孤立点，对答案没有影响。

• 若 $G$ 为无向连通图，$d$ 为偶数，则 $G$ 有欧拉回路。
  • 证明：在欧拉回路中，有进必有出，每次走 $u$ 都使 $d(u)$ 减少 $2$。
• 若 $G$ 为无向连通图，其中只有 $d(u),d(v)$ 为奇数，其余 $d$ 为偶数，则 $G$ 有欧拉路径。
• 若 $G$ 为有向图且基图连通，$d^+=d-$，则 $G$ 有欧拉回路。
• 若 $G$ 为有向图且基图连通，其中只有 $d^+(u)=d-(u)+1,d^+(v)+1=d-(v)$，其余 $d^+=d-$，则 $G$ 有欧拉路径。

（基图：忽略有向图边的方向，得到的无向图。）

小 trick：无向连通图中只有偶数个 $d$ 为奇数的点。

证明：每一条边都为两端的 $d$ 加上 $1$，反证即可。

实现

非常 naive 地写出这样的东西：

void euler(int u){
		for(int i=g.head[u];i;i=g.nxt[i]){
			int v=g[i].v;
			if(vis[i]) continue;
			vis[i]=1;
			euler(v);
			ans[++cnt]=i;
		}
	}

本质上就是找环，找很多很多个环，把它们套在一起（套圈法）。