[筆記]歐拉圖

定義

• 歐拉路徑是每條邊恰好經過一次的路徑；存在歐拉路徑的圖是半歐拉圖。
• 歐拉回路是每條邊恰好經過一次的回路；存在歐拉回路的圖是歐拉圖。

判定

• 無向圖是歐拉圖\(\iff\)非零度節(jié)點連通，所有節(jié)點度數為偶。此時起點可以選任意節(jié)點。
• 無向圖是半歐拉圖\(\iff\)非零度節(jié)點連通，恰有\(2\)個節(jié)點度數為奇。此時起點可以選兩個奇度節(jié)點之一。
• 有向圖是歐拉圖\(\iff\)非零度節(jié)點強連通，每個節(jié)點出入度相等。此時起點可以選任意節(jié)點。
• 有向圖是半歐拉圖\(\iff\)非零度節(jié)點弱連通，至多一個頂點出度\(-\)入度\(=1\)，至多一個頂點入度\(-\)出度\(=1\)，其他節(jié)點出入度相等。此時起點是那個出度\(-\)入度\(=1\)的節(jié)點。

例題：

• 有向圖：UVA10129 單詞 Play on Words ~ 題解
• 無向圖：P1333 瑞瑞的木棍 ~ 題解

輸出

下文中，將要輸出的內容存入棧st中，輸出時逐個彈棧即可；p初始全為\(0\)。

由于要求按最小字典序輸出，所以需要對出邊從小到大排序，因此使用了鄰接表存儲。

輸出途徑點（有向圖） - P7771 【模板】歐拉路徑

void dfs(int u){
	for(int i=p[u];i<out[u];i=p[u]){
		p[u]++;
		dfs(G[u][i]);
	}
	st.push(u);
}

輸出途徑點（無向圖） - P2731 [USACO3.3] 騎馬修柵欄 Riding the Fences

void dfs(int u){
	for(int i=p[u];i<out[u];i=p[u]){
		p[u]++;
		if(cnt[u][v]) cnt[u][v]--,cnt[v][u]--,dfs(G[u][i]);
	}
	st.push(u);
}

輸出途徑邊（有向圖） - P1127 詞鏈

void dfs(int u){
	for(int i=p[u];i<out[u];i=p[u]){
		p[u]++;
		dfs(G[u][i].to);
		st.push(G[u][i].id);
	}
}

輸出途徑邊（無向圖） - [暫無]

void dfs(int u){
	for(int i=p[u];i<out[u];i=p[u]){
		p[u]++;
		if(cnt[u][v]) cnt[u][v]--,cnt[v][u]--,dfs(G[u][i].to);
		st.push(G[u][i].id);
	}
}