MENU

UOJ#117/LibreOJ#10105 欧拉回路

UOJ#117

LibreOJ#10105

是否存在欧拉回路:

  • 无向图:所有点度数均为偶数
  • 有向图:所有点入度均等于出度

寻找方案(在有解的前提下):神秘的“套d圈f法s”,每条路递归到头后记录。记下来的是反的,逆序输出。

随手加一波当前弧优化不然会T。

#include<cstdio>
#include<cstring>
#include<stack>
#ifdef WIN32
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#else
#define fread fread_unlocked
#endif
using namespace std;
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT;
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T = int>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
}ip;
int t = ip.rd(), n = ip.rd(), m = ip.rd(), cnt, head[100001], sz[100001], vis[400001];
struct edge {
    int v, next;
    edge(int v = 0, int next = 0) :v(v), next(next) {}
}e[400001];
inline void addedge(int u, int v) { e[++cnt] = edge(v, head[u]), head[u] = cnt; }
stack<int>s;
inline void dfs1(int x) {
    int now;
    while (now = head[x])if (!vis[now])vis[now] = vis[now ^ 1] = 1, dfs1(e[now].v), s.push(now & 1 ? -(now >> 1) : now >> 1);
        else head[x] = e[now].next;
}
inline void dfs2(int x) {
    int now;
    while (now = head[x])if (!vis[now])vis[now] = 1, dfs2(e[now].v), s.push(now);
        else head[x] = e[now].next;
}
int main() {
    int begin = 0;
    if (t == 1) {
        cnt = 1;
        for (int i = 1; i <= m; ++i) {
            int u = begin = ip.rd(), v = ip.rd();
            addedge(u, v), addedge(v, u), ++sz[u], ++sz[v];
        }
        for (int i = 1; i <= n; ++i)if (sz[i] & 1)return puts("NO"), 0;
        dfs1(begin);
    }
    else {
        for (int i = 1; i <= m; ++i) {
            int u = begin = ip.rd(), v = ip.rd();
            addedge(u, v), --sz[u], ++sz[v];
        }
        for (int i = 1; i <= n; ++i)if (sz[i])return puts("NO"), 0;
        dfs2(begin);
    }
    if (s.size() != m)return puts("NO"), 0;
    puts("YES");
    while (s.size())printf("%d ", s.top()), s.pop();
}