歐拉環：圖中經過每條邊一次且僅一次的環；
歐拉路徑：圖中經過每條邊一次且僅一次的路徑；
歐拉圖：有至少一個歐拉環的圖；
半歐拉圖：沒有歐拉環，但有至少一條歐拉路徑的圖。
【無向圖】
一個無向圖是歐拉圖當且僅當該圖是連通的（注意，不考慮圖中度為0的點，因為它們的存在對于圖中是否存在歐拉環、歐拉路徑沒有影響）且所有點的度數都是偶數；一個無向圖是半歐拉圖當且僅當該圖是連通的且有且只有2個點的度數是奇數（此時這兩個點只能作為歐拉路徑的起點和終點）；
證明：因為任意一個點，歐拉環（或歐拉路徑）從它這里進去多少次就要出來多少次，故(進去的次數+出來的次數)為偶數，又因為(進去的次數+出來的次數)=該點的度數（根據定義），所以該點的度數為偶數。
【有向圖】
一個有向圖是歐拉圖當且僅當該圖的基圖（將所有有向邊變為無向邊后形成的無向圖，這里同樣不考慮度數為0的點）是連通的且所有點的入度等于出度；一個有向圖是半歐拉圖當且僅當該圖的基圖是連通的且有且只有一個點的入度比出度少1（作為歐拉路徑的起點），有且只有一個點的入度比出度多1（作為終點），其余點的入度等于出度。
證明：與無向圖證明類似，一個點進去多少次就要出來多少次。
【無向圖、有向圖中歐拉環的求法】
與二分圖匹配算法類似，是一個深度優先遍歷的過程，時間復雜度O(M)（因為一條邊最多被訪問一次）。核心代碼（邊是用邊表存儲的而不是鄰接鏈表，因為無向圖中需要對其逆向的邊進行處理，在有向圖中，可以用鄰接鏈表存儲邊）：
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中寫入是逆序的，所以初始的v應設成(邊數-1)。
但是有一個問題是，這是遞歸實現的，當點數過多時有爆棧危險，所以最好使用非遞歸：
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];
}
}
}
當原圖是歐拉圖時，一定可以求出歐拉回路。當原圖是半歐拉圖時，求歐拉路徑，只要找到起點i和終點j，添加邊<j, i>（或(j, i)），求歐拉環，再在求出的歐拉環中刪除添加的新邊即可。
不過最為BT的還不是這個，而是接下來的——
【混合圖】
混合圖（既有有向邊又有無向邊的圖）中歐拉環、歐拉路徑的判定需要借助網絡流！
（1）歐拉環的判定：
一開始當然是判斷原圖的基圖是否連通，若不連通則一定不存在歐拉環或歐拉路徑（不考慮度數為0的點）。
其實，難點在于圖中的無向邊，需要對所有的無向邊定向（指定一個方向，使之變為有向邊），使整個圖變成一個有向歐拉圖（或有向半歐拉圖）。若存在一個定向滿足此條件，則原圖是歐拉圖（或半歐拉圖）否則不是。關鍵就是如何定向？
首先給原圖中的每條無向邊隨便指定一個方向（稱為初始定向），將原圖改為有向圖G'，然后的任務就是改變G'中某些邊的方向（當然是無向邊轉化來的，原混合圖中的有向邊不能動）使其滿足每個點的入度等于出度。
設D[i]為G'中(點i的出度 - 點i的入度）。可以發現，在改變G'中邊的方向的過程中，任何點的D值的奇偶性都不會發生改變（設將邊<i, j>改為<j, i>，則i入度加1出度減1，j入度減1出度加1，兩者之差加2或減2，奇偶性不變）！而最終要求的是每個點的入度等于出度，即每個點的D值都為0，是偶數，故可得：若初始定向得到的G'中任意一個點的D值是奇數，那么原圖中一定不存在歐拉環！
若初始D值都是偶數，則將G'改裝成網絡：設立源點S和匯點T，對于每個D[i]>0的點i，連邊<S, i>，容量為D[i]/2；對于每個D[j]<0的點j，連邊<j, T>，容量為-D[j]/2；G'中的每條邊在網絡中仍保留，容量為1（表示該邊最多只能被改變方向一次）。求這個網絡的最大流，若S引出的所有邊均滿流，則原混合圖是歐拉圖，將網絡中所有流量為1的中間邊（就是不與S或T關聯的邊）在G'中改變方向，形成的新圖G''一定是有向歐拉圖；若S引出的邊中有的沒有滿流，則原混合圖不是歐拉圖。
為什么能這樣建圖？
考慮網絡中的一條增廣路徑S-->i-->...-->j-->T，將這條從i到j的路徑在G'中全部反向，則：i的入度加1出度減1，j的入度減1出度加1，路徑中其它點的入度出度均不變。而i是和S相連的，因此初始D[i]>0，即i的出度大于入度，故這樣反向之后D[i]減少2；同理，j是和T相連的，這樣反向之后D[j]增加2。因此，若最大流中邊<S, i>滿流（流量為初始D[i]/2），此時D[i]值就變成了0，也就是i的入度等于出度。因此只要使所有S引出的邊全部滿流，所有初始D值>0的點的D值將等于0，又因為將邊變向后所有點的D值之和不變，所有初始D值小于0的點的D值也將等于0，而初始D值等于0的D點既不與S相連也不與T相連，所以它們是網絡中的中間點，而中間點的流入量等于流出量，故它們的入度和出度一直不變，即D值一直為0。因此，整個圖G'成為歐拉圖。
（2）歐拉路徑的判定：
首先可以想到的是枚舉歐拉路徑的起點i和終點j，然后在圖中添加邊<j, i>，再求圖中是否有歐拉回路即可。但是，該算法的時間復雜度達到了O(M * 最大流的時間)，需要優化。
前面已經說過，在將邊變向的過程中任何點的D值的奇偶性都不會改變，而一個有向圖有歐拉路徑的充要條件是基圖連通且有且只有一個點的入度比出度少1（作為歐拉路徑的起點），有且只有一個點的入度比出度多1（作為終點），其余點的入度等于出度。這就說明，先把圖中的無向邊隨便定向，然后求每個點的D值，若有且只有兩個點的初始D值為奇數，其余的點初始D值都為偶數，則有可能存在歐拉路徑（否則不可能存在）。進一步，檢查這兩個初始D值為奇數的點，設為點i和點j，若有D[i]>0且D[j]<0，則i作起點j作終點（否則若D[i]與D[j]同號則不存在歐拉路徑），連邊<j, i>，求是否存在歐拉環即可（將求出的歐拉環中刪去邊<j, i>即可）。這樣只需求一次最大流。
【典型例題】Sightseeing tour（PKU1637，ZJU1992）
本題就是求混合圖的歐拉環問題，題目中已經說明圖是連通的（Input的最后一句話），故不需判連通。
（本沙茶一開始把DFS中的l0 = aug中的"= aug"寫漏了，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;
}