歐拉路與歐拉回路 && UOJ #117. 歐拉回路

下面的定義都是個人了解

歐拉路：從一個點走到另外一個點，圖中每條邊都隻經過一次

歐拉回路：在歐拉路的基礎上，要求終點和起點相同

歐拉路與歐拉回路的判斷

對于無向圖

• 隻有兩個點的度數是1，這兩個點分别為起點和終點，則這個無向圖存在歐拉路
• 每個點的度數都為偶數，則這個無向圖存在歐拉回路

對于有向圖

• 有一個點的入度比出度多1作為終點，還有一個點的出度比入度多1作為起點，其餘點的入度和出度相同，則這個有向圖存在歐拉路
• 所有點的入度和出度相同，則這個有向圖存在歐拉回路

求歐拉回路

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
struct node {int next, to, w;}e[A];
int head[A], num = 1;
void add(int fr, int to, int w) {e[++num].next = head[fr]; e[num].to = to; e[num].w = w; head[fr] = num;}
int t, n, m, a, b, in[A], out[A], cnt, ans[A]; bool vis[A];
void dfs(int fr) {
  for (int &i = head[fr]; i; i = e[i].next) {
    node t = e[i];
    if (vis[i >> 1]) continue;
    vis[i >> 1] = 1;
    dfs(t.to);
    ans[++cnt] = t.w;
  }
}

int main(int argc, char const *argv[]) {
  cin >> t >> n >> m;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a, &b);
    add(a, b, i); in[b]++; out[a]++;
    if (t == 1) add(b, a, -i); else num++;
  }
  bool ok = 1;
  if (t == 1) {
    for (int i = 1; i <= n; i++) if ((in[i] + out[i]) % 2) {ok = 0; break;}
  }
  else for (int i = 1; i <= n; i++) if (in[i] != out[i]) {ok = 0; break;}
  if (ok) {
    dfs(a);
    if (cnt != m) puts("NO");
    else {
      puts("YES");
      for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]);
    }
  }
  else puts("NO");
}