歐拉環(huán)：圖中經(jīng)過(guò)每條邊一次且僅一次的環(huán)；
歐拉路徑：圖中經(jīng)過(guò)每條邊一次且僅一次的路徑；
歐拉圖：有至少一個(gè)歐拉環(huán)的圖；
半歐拉圖：沒(méi)有歐拉環(huán)，但有至少一條歐拉路徑的圖。
【無(wú)向圖】
一個(gè)無(wú)向圖是歐拉圖當(dāng)且僅當(dāng)該圖是連通的（注意，不考慮圖中度為0的點(diǎn)，因?yàn)樗鼈兊拇嬖趯?duì)于圖中是否存在歐拉環(huán)、歐拉路徑?jīng)]有影響）且所有點(diǎn)的度數(shù)都是偶數(shù)；一個(gè)無(wú)向圖是半歐拉圖當(dāng)且僅當(dāng)該圖是連通的且有且只有2個(gè)點(diǎn)的度數(shù)是奇數(shù)（此時(shí)這兩個(gè)點(diǎn)只能作為歐拉路徑的起點(diǎn)和終點(diǎn)）；
證明：因?yàn)槿我庖粋€(gè)點(diǎn)，歐拉環(huán)（或歐拉路徑）從它這里進(jìn)去多少次就要出來(lái)多少次，故(進(jìn)去的次數(shù)+出來(lái)的次數(shù))為偶數(shù)，又因?yàn)?進(jìn)去的次數(shù)+出來(lái)的次數(shù))=該點(diǎn)的度數(shù)（根據(jù)定義），所以該點(diǎn)的度數(shù)為偶數(shù)。
【有向圖】
一個(gè)有向圖是歐拉圖當(dāng)且僅當(dāng)該圖的基圖（將所有有向邊變?yōu)闊o(wú)向邊后形成的無(wú)向圖，這里同樣不考慮度數(shù)為0的點(diǎn)）是連通的且所有點(diǎn)的入度等于出度；一個(gè)有向圖是半歐拉圖當(dāng)且僅當(dāng)該圖的基圖是連通的且有且只有一個(gè)點(diǎn)的入度比出度少1（作為歐拉路徑的起點(diǎn)），有且只有一個(gè)點(diǎn)的入度比出度多1（作為終點(diǎn)），其余點(diǎn)的入度等于出度。
證明：與無(wú)向圖證明類似，一個(gè)點(diǎn)進(jìn)去多少次就要出來(lái)多少次。
【無(wú)向圖、有向圖中歐拉環(huán)的求法】
與二分圖匹配算法類似，是一個(gè)深度優(yōu)先遍歷的過(guò)程，時(shí)間復(fù)雜度O(M)（因?yàn)橐粭l邊最多被訪問(wèn)一次）。核心代碼（邊是用邊表存儲(chǔ)的而不是鄰接鏈表，因?yàn)闊o(wú)向圖中需要對(duì)其逆向的邊進(jìn)行處理，在有向圖中，可以用鄰接鏈表存儲(chǔ)邊）：
void dfs(int x)
{
int y;
for (int p=hd[x]; p != -1; p=ed[p].next) if (!ed[p].vst) {
y = ed[p].b;
ed[p].vst = 1;
ed[p ^ 1].vst = 1; //如果是有向圖則不要這句
dfs(y);
res[v--] = y + 1;
}
}
要注意的是在res中寫(xiě)入是逆序的，所以初始的v應(yīng)設(shè)成(邊數(shù)-1)。
但是有一個(gè)問(wèn)題是，這是遞歸實(shí)現(xiàn)的，當(dāng)點(diǎn)數(shù)過(guò)多時(shí)有爆棧危險(xiǎn)，所以最好使用非遞歸：
void dfs()
{
int x = 0, y, tp = 1; stk[0] = 0;
re(i, n) now[i] = hd[i];
bool ff;
while (tp) {
ff = 0;
for (int p=now[x]; p != -1; p=ed[p].next) if (!ed[p].vst) {
y = ed[p].b;
ed[p].vst = 1;
ed[p ^ 1].vst = 1; //如果是有向圖則不要這句
now[x] = p; stk[tp++] = y; x = y; ff = 1; break;
}
if (!ff) {
res[v--] = x + 1;
x = stk[--tp - 1];
}
}
}
當(dāng)原圖是歐拉圖時(shí)，一定可以求出歐拉回路。當(dāng)原圖是半歐拉圖時(shí)，求歐拉路徑，只要找到起點(diǎn)i和終點(diǎn)j，添加邊<j, i>（或(j, i)），求歐拉環(huán)，再在求出的歐拉環(huán)中刪除添加的新邊即可。
不過(guò)最為BT的還不是這個(gè)，而是接下來(lái)的——
【混合圖】
混合圖（既有有向邊又有無(wú)向邊的圖）中歐拉環(huán)、歐拉路徑的判定需要借助網(wǎng)絡(luò)流！
（1）歐拉環(huán)的判定：
一開(kāi)始當(dāng)然是判斷原圖的基圖是否連通，若不連通則一定不存在歐拉環(huán)或歐拉路徑（不考慮度數(shù)為0的點(diǎn)）。
其實(shí)，難點(diǎn)在于圖中的無(wú)向邊，需要對(duì)所有的無(wú)向邊定向（指定一個(gè)方向，使之變?yōu)橛邢蜻叄拐麄€(gè)圖變成一個(gè)有向歐拉圖（或有向半歐拉圖）。若存在一個(gè)定向滿足此條件，則原圖是歐拉圖（或半歐拉圖）否則不是。關(guān)鍵就是如何定向？
首先給原圖中的每條無(wú)向邊隨便指定一個(gè)方向（稱為初始定向），將原圖改為有向圖G'，然后的任務(wù)就是改變G'中某些邊的方向（當(dāng)然是無(wú)向邊轉(zhuǎn)化來(lái)的，原混合圖中的有向邊不能動(dòng)）使其滿足每個(gè)點(diǎn)的入度等于出度。
設(shè)D[i]為G'中(點(diǎn)i的出度 - 點(diǎn)i的入度）。可以發(fā)現(xiàn)，在改變G'中邊的方向的過(guò)程中，任何點(diǎn)的D值的奇偶性都不會(huì)發(fā)生改變（設(shè)將邊<i, j>改為<j, i>，則i入度加1出度減1，j入度減1出度加1，兩者之差加2或減2，奇偶性不變）！而最終要求的是每個(gè)點(diǎn)的入度等于出度，即每個(gè)點(diǎn)的D值都為0，是偶數(shù)，故可得：若初始定向得到的G'中任意一個(gè)點(diǎn)的D值是奇數(shù)，那么原圖中一定不存在歐拉環(huán)！
若初始D值都是偶數(shù)，則將G'改裝成網(wǎng)絡(luò)：設(shè)立源點(diǎn)S和匯點(diǎn)T，對(duì)于每個(gè)D[i]>0的點(diǎn)i，連邊<S, i>，容量為D[i]/2；對(duì)于每個(gè)D[j]<0的點(diǎn)j，連邊<j, T>，容量為-D[j]/2；G'中的每條邊在網(wǎng)絡(luò)中仍保留，容量為1（表示該邊最多只能被改變方向一次）。求這個(gè)網(wǎng)絡(luò)的最大流，若S引出的所有邊均滿流，則原混合圖是歐拉圖，將網(wǎng)絡(luò)中所有流量為1的中間邊（就是不與S或T關(guān)聯(lián)的邊）在G'中改變方向，形成的新圖G''一定是有向歐拉圖；若S引出的邊中有的沒(méi)有滿流，則原混合圖不是歐拉圖。
為什么能這樣建圖？
考慮網(wǎng)絡(luò)中的一條增廣路徑S-->i-->...-->j-->T，將這條從i到j(luò)的路徑在G'中全部反向，則：i的入度加1出度減1，j的入度減1出度加1，路徑中其它點(diǎn)的入度出度均不變。而i是和S相連的，因此初始D[i]>0，即i的出度大于入度，故這樣反向之后D[i]減少2；同理，j是和T相連的，這樣反向之后D[j]增加2。因此，若最大流中邊<S, i>滿流（流量為初始D[i]/2），此時(shí)D[i]值就變成了0，也就是i的入度等于出度。因此只要使所有S引出的邊全部滿流，所有初始D值>0的點(diǎn)的D值將等于0，又因?yàn)閷⑦呑兿蚝笏悬c(diǎn)的D值之和不變，所有初始D值小于0的點(diǎn)的D值也將等于0，而初始D值等于0的D點(diǎn)既不與S相連也不與T相連，所以它們是網(wǎng)絡(luò)中的中間點(diǎn)，而中間點(diǎn)的流入量等于流出量，故它們的入度和出度一直不變，即D值一直為0。因此，整個(gè)圖G'成為歐拉圖。
（2）歐拉路徑的判定：
首先可以想到的是枚舉歐拉路徑的起點(diǎn)i和終點(diǎn)j，然后在圖中添加邊<j, i>，再求圖中是否有歐拉回路即可。但是，該算法的時(shí)間復(fù)雜度達(dá)到了O(M * 最大流的時(shí)間)，需要優(yōu)化。
前面已經(jīng)說(shuō)過(guò)，在將邊變向的過(guò)程中任何點(diǎn)的D值的奇偶性都不會(huì)改變，而一個(gè)有向圖有歐拉路徑的充要條件是基圖連通且有且只有一個(gè)點(diǎn)的入度比出度少1（作為歐拉路徑的起點(diǎn)），有且只有一個(gè)點(diǎn)的入度比出度多1（作為終點(diǎn)），其余點(diǎn)的入度等于出度。這就說(shuō)明，先把圖中的無(wú)向邊隨便定向，然后求每個(gè)點(diǎn)的D值，若有且只有兩個(gè)點(diǎn)的初始D值為奇數(shù)，其余的點(diǎn)初始D值都為偶數(shù)，則有可能存在歐拉路徑（否則不可能存在）。進(jìn)一步，檢查這兩個(gè)初始D值為奇數(shù)的點(diǎn)，設(shè)為點(diǎn)i和點(diǎn)j，若有D[i]>0且D[j]<0，則i作起點(diǎn)j作終點(diǎn)（否則若D[i]與D[j]同號(hào)則不存在歐拉路徑），連邊<j, i>，求是否存在歐拉環(huán)即可（將求出的歐拉環(huán)中刪去邊<j, i>即可）。這樣只需求一次最大流。
【典型例題】Sightseeing tour（PKU1637，ZJU1992）
本題就是求混合圖的歐拉環(huán)問(wèn)題，題目中已經(jīng)說(shuō)明圖是連通的（Input的最后一句話），故不需判連通。
（本沙茶一開(kāi)始把DFS中的l0 = aug中的"= aug"寫(xiě)漏了，TLE了N次）
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 2002, MAXM = 10000, INF = ~0U >> 2;
struct edge {
int a, b, f, next;
edge () {}
edge (int _a, int _b, int _f): a(_a), b(_b), f(_f), next(-1) {}
} ed[MAXM + MAXM];
int n, m, s, t, D[MAXN], hd[MAXN], tl[MAXN], lb[MAXN], vl[MAXN], flow, lmt;
bool res;
int dfs(int i, int aug)
{
if (i == t) {flow += aug; return aug;}
int l0 = aug, l1, j, f0;
for (int p=hd[i]; p != -1; p=ed[p].next) {
j = ed[p].b; f0 = ed[p].f;
if (lb[i] == lb[j] + 1 && f0) {
l1 = dfs(j, l0 <= f0 ? l0 : f0);
l0 -= l1; ed[p].f -= l1; ed[p ^ 1].f += l1;
if (lb[s] == n || !l0) return aug;
}
}
int minlb = n - 1;
for (int p=hd[i]; p != -1; p=ed[p].next) if (ed[p].f) {
j = ed[p].b;
if (lb[j] < minlb) minlb = lb[j];
}
if (--vl[lb[i]]) vl[lb[i] = minlb + 1]++; else lb[s] = n;
return aug - l0;
}
inline void add_edge(int a, int b, int f)
{
ed[m] = edge(a, b, f);
if (hd[a] != -1) tl[a] = ed[tl[a]].next = m++; else hd[a] = tl[a] = m++;
ed[m] = edge(b, a, 0);
if (hd[b] != -1) tl[b] = ed[tl[b]].next = m++; else hd[b] = tl[b] = m++;
}
void solve()
{
int tests;
scanf("%d", &tests);
int n0, m0, a0, b0, f;
re(testno, tests) {
scanf("%d%d", &n0, &m0);
n = n0 + 2; m = 0; s = 0; t = n - 1;
memset(D, 0, n0 << 2); memset(hd, -1, n << 2); memset(tl, -1, n << 2);
re(i, m0) {
scanf("%d%d%d", &a0, &b0, &f);
D[a0 - 1]++; D[b0 - 1]--;
if (!f) add_edge(a0, b0, 1);
}
res = 1; lmt = 0; flow = 0;
re(i, n0) {
if (D[i] % 2) {res = 0; break;}
if (D[i] > 0) {add_edge(s, i + 1, D[i] >> 1); lmt += D[i] >> 1;}
if (D[i] < 0) add_edge(i + 1, t, -D[i] >> 1);
}
if (res) {
memset(lb, 0, n << 2); vl[0] = n; memset(vl + 1, 0, n << 2);
while (lb[s] < n) dfs(s, INF);
if (flow < lmt) res = 0;
}
puts(res ? "possible" : "impossible");
}
}
int main()
{
solve();
return 0;
}