「POI 2011」Garbage

题目大意：

可以发现不需要改变的边是没有影响的，直接删掉即可，剩下的边无向图欧拉回路找环。

#include <cstdio>

const int N = 100005, M = 2000005;
int head[N], nxt[M], pnt[M], tot = 1, d[N], dfn[N], ins[N], vis[M], sta[N], top, e[M], ecnt, ans[M<<1], cnt;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void add_edge(int u, int v) {
    nxt[++tot] = head[u];
    head[u] = tot, pnt[tot] = v;
}
void dfs(int cur) {
    dfn[cur] = 1;
    for (int &i = head[cur], j; i; i = nxt[i]) { //当前弧优化
        if (vis[(j=i)>>1]) continue;
        vis[j>>1] = 1, dfs(pnt[j]), e[++ecnt] = j;
    }
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), s = read(), t = read();
        if (s ^ t) add_edge(u, v), add_edge(v, u), ++d[u], ++d[v];
    }
    for (int i = 1; i <= n; ++i)
        if (d[i] & 1) { puts("NIE"); return 0; }
    for (int i = 1; i <= n; ++i) { //可能图不连通
        if (dfn[i]) continue;
        dfs(i), sta[top=1] = i, ins[i] = 1;
        while (ecnt) {
            int j = e[ecnt];
            if (ins[pnt[j]]) {
                ++ans[0], ans[++cnt] = 1;
                for (int k = top; sta[k] != pnt[j]; --k)
                    ++ans[cnt];
                ans[++cnt] = pnt[j];
                while (sta[top] != pnt[j])  
                    ans[++cnt] = sta[top], ins[sta[top--]] = 0; //别忘记把ins标记为0
                ans[++cnt] = pnt[j];
            } else sta[++top] = pnt[j], ins[pnt[j]] = 1;
            --ecnt;
        }
    }
    printf("%d", ans[0]);
    for (int i = 1, j = 0; i <= cnt; ++i) {
        if (j == 0) j = ans[i] + 1, printf("\n%d ", ans[i]);
        else --j, printf("%d ", ans[i]);
    }
    return 0;
}

时间复杂度 $O(n+m)$