HDU 6311 Cover 多条欧拉回路

题意：给你一个无向图。求最少多少条路径，可以完全覆盖所有边，并且没有重复

题解：

假如一条路径覆盖所有边， 此时即为欧拉路径。现在不是欧拉图，需要多少条路径同理。

欧拉路径要求仅两个点度数为奇数。现在我们统计奇数点的个数d，答案即为max(d/2, 1)。

我们可以把每两个奇数点再连一条边，此时即会构成一条欧拉回路。删除这些边后会构成d/2条路径。

跑一边欧拉回路算法找出路径，然后分段输出即可。

但有个问题，有可能会跑出结果大于d/2。这是因为是按照了特定的路径跑的时候出现的特例。

绿色为起点，红色为新增的边，按照如图方向跑的话，最终会分隔出3条路径，实际上是2条。

那么我们对于这种新加了边的图，少加一条边，使得从奇数点开始跑，跑到另一个奇数点，这样子不会出现问题。原理我也不懂。

代码：

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int MAXN = 1e5 + 5;

int stk[MAXN * 5];
bool vis[MAXN * 5]; // 边vis
int bj;

struct Edge {
    int v, nxt, id;
} e[MAXN * 5];

int tot, cnt;
int head[MAXN], deg[MAXN], used[MAXN], used2[MAXN];
int nd[MAXN];

void add (int x, int y, int id) {
    e[tot++] = {y, head[x], id};
    head[x] = tot - 1;
}

void dfs2(int now) {
    if(deg[now] & 1) nd[cnt++] = now;
    used2[now] = 1;
    for(int i = head[now]; ~i; i = e[i].nxt) {
        if(!used2[e[i].v]) dfs2(e[i].v);
    }
}


void dfs (int now) {
    nd[cnt++] = now;
    used[now] = 1;
    for (int i = head[now]; i != -1; i = e[i].nxt) {
        if (!vis[i]) {
            vis[i] = 1;
            vis[i ^ 1] = 1;
            dfs (e[i].v);
            stk[bj++] = i;
        }
    }
}


int main() {
#ifdef LOCAL
    freopen ("input.txt", "r", stdin);
#endif
    int n, m;
    while (~scanf ("%d %d", &n, &m) ) {

        memset (vis, 0, sizeof (vis) );
        memset (head, -1, sizeof (head) );
        memset (deg, 0, sizeof (deg) );
        memset (used, 0, sizeof (used) );
        memset (used2, 0, sizeof(used2));
        bj = tot = 0;

        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf ("%d %d", &x, &y);
            add (x, y, i);
            add (y, x, -i);
            deg[x]++; deg[y]++;
        }

//        queue<int> q;
//        for (int i = 1; i <= n; i++) {
//            if (deg[i] % 2 == 1) {
//                if (q.size() ) {
//                    add (q.front(), i, m + 1);
//                    add (i, q.front(), m + 1);
//                    q.pop();
//                } else q.push (i);
//            }
//        }
        vector< vector<int> > path;
        for (int i = 1; i <= n; i++) {
            if (deg[i] && !used[i]) {
                bj = cnt = 0;
                dfs2(i);
                for(int j = 2; j < cnt - 1; j += 2) {
                    add(nd[j], nd[j + 1], m + 1);
                    add(nd[j + 1], nd[j], m + 1);
                }
                if(cnt > 0) dfs(nd[0]);
                else dfs (i);
                vector<int> t;
                for (int j = bj - 1; j >= 0; j--) {
                    if (e[stk[j]].id == m + 1) {
                        if (t.size()) path.push_back (t), t.clear();
                    } else t.push_back (e[stk[j]].id);
                }
                if(t.size()) path.push_back(t);
            }
        }
        printf ("%d\n", path.size() );
        for (auto &p : path) {
            printf ("%d ", p.size() );
            for (int i = 0; i < p.size(); i++) {
                printf ("%d%c", p[i], " \n"[i == p.size() - 1]);
            }
        }
    }
    return 0;
}