標題鏈接

題意

• 給一張圖，當結(jié)點u，v的度不都是奇數(shù)時，我們可以刪掉落結(jié)點u，v之間的邊。問：最多能刪掉落若干條邊，并按照刪除的次序輸出邊的序號。標題不包管圖是連通的，然則包管所有點的度在初始時都為偶數(shù)，也就是包管每個連通塊都是一個歐拉回路。

思路

• 對于一個歐拉回路，我們先假裝刪除一條邊讓其變成一個歐拉通路，此時存在兩個奇數(shù)度點。我們選擇一個作為起點，一個作為終點。我們 dfs 大年夜起點遍歷到終點，在回溯時才往棧中存邊，那么大年夜棧底到棧頂就是精確的┞俘當路徑。問題是怎么找到這個路徑呢？
• 在歐拉通路中刪邊時，我們老是可以包管只有兩個奇數(shù)點。應(yīng)用這個性質(zhì)，我們跑全部歐拉回路，按照回溯存邊的辦法將所有的邊推入棧。我們大年夜棧底開端刪邊，如不雅合軌則刪除。
• 如不雅棧底的邊的兩個結(jié)點都是奇數(shù)點：其拭魅這個時刻只有一種情況并且只會出現(xiàn)一次，就是這條邊有一個點是起點。如不雅這個時刻未跑的邊數(shù)大年夜于1，那么起點必定還有一個邊 x 連接著偶數(shù)點，這個時刻我們可以刪除邊 x 以詞攀來改變起點的奇偶性。所以這個時刻我們可以刪除棧頂?shù)倪?#xff0c;也就是將奇數(shù)點綴移。（為什么棧頂?shù)倪吺强梢缘?#xff1f;因為最后一條邊必定是連接到起點的，跑歐拉回路最終要回到起點的嘛。）如許我們最后只會剩下一條邊。

Code

#include <iostream>
#include <cstdio>
using namespace std;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int maxN = 500005;
int du[maxN];
bool vis[maxN];
int n, m;
struct EDGE{
    int adj, to, id;
    EDGE(int a = -1, int b = 0, int c = 0): adj(a), to(b), id(c) {}
}edge[maxN << 1];
int head[maxN], cnt;
void init() {
    cnt = 0;
    for(int i = 0; i <= n; ++ i ) {
        head[i] = -1;
        du[i] = 0;
    }
    for(int i = 0; i <= m; ++ i ) {
        vis[i] = false;
    }
}
void add_edge(int u, int v, int id) {
    edge[cnt] = EDGE(head[u], v, id);
    head[u] = cnt ++ ;
}
pair<int, int>pi[maxN];
int Stack[maxN], ans[maxN], top, tot;
void dfs(int u) {
    while(~head[u]) {
        int i = head[u];
        int v = edge[i].to;
        int id = edge[i].id;
        head[u] = edge[i].adj;
        if(vis[id]) continue;
        vis[id] = true;
        dfs(v);
        Stack[++top] = id;
    }
}
void solve() {
    int l = 1, r = top;
    while(l < r) {
        int u = pi[Stack[l]].first, v = pi[Stack[l]].second;
        if(du[u] & 1 && du[v] & 1) {
            ans[++ tot] = Stack[r];
            u = pi[Stack[r]].first, v = pi[Stack[r]].second;
            -- r;
        } else {
            ans[ ++ tot] = Stack[l];
            ++ l;
        }
        -- du[u], -- du[v];
    }
}
int main() {
    n = read(), m = read();
    init();
    for(int i = 1; i <= m; ++ i ) {
        int u, v;
        u = read(), v = read();
        add_edge(u, v, i);
        add_edge(v, u, i);
        pi[i] = make_pair(u, v);
        ++ du[u], ++ du[v];
    }
    for(int i = 1; i <= n; ++ i ) {
        top = 0;
        dfs(i);
        if(top) {
            solve();
        }
    }
    printf("%d\n", tot);
    for(int i = 1; i <= tot; ++ i ) {
        printf("%d%c", ans[i], (i == tot ? '\n' : ' '));
    }
    return 0;
}

/*
12 16
1 2
1 3
1 11
1 12
2 4
2 5
2 3
4 8
5 9
8 9
3 6
3 7
6 9
7 10
11 12
9 10
 ans:
15
1 5 8 10 9 6 7 11 13 16 14 12 4 2 3

14 19
1 2
1 3
1 11
1 12
2 4
2 5
2 3
4 8
5 9
8 9
3 6
3 7
6 9
7 10
11 12
9 10
1 13
1 14
13 14
 ans:
18
1 5 8 10 9 6 7 11 13 16 14 12 18 2 3 15 4 17
 */