題目鏈接
題意
- 給一張圖，當結點u，v的度不都是奇數時，我們可以刪掉結點u，v之間的邊，問：最多能刪掉多少條邊，并按照洗掉的順序輸出邊的序號，題目不保證圖是連通的，但是保證所有點的度在初始時都為偶數，也就是保證每個連通塊都是一個歐拉回路，
思路
- 對于一個歐拉回路，我們先假裝洗掉一條邊讓其變成一個歐拉通路，此時存在兩個奇數度點，我們選擇一個作為起點，一個作為終點，我們 dfs 從起點遍歷到終點，在回溯時才往堆疊中存邊，那么從堆疊底到堆疊頂就是正確的合法路徑，問題是怎么找到這個路徑呢？
- 在歐拉通路中刪邊時，我們總是可以保證只有兩個奇數點，利用這個性質，我們跑整個歐拉回路，按斬訓溯存邊的方法將所有的邊推入堆疊，我們從堆疊底開始刪邊，如果合法則洗掉，
- 如果堆疊底的邊的兩個結點都是奇數點：其實這個時候只有一種情況并且只會出現一次，就是這條邊有一個點是起點，如果這個時候未跑的邊數大于1，那么起點一定還有一個邊 x 連接著偶數點，這個時候我們可以洗掉邊 x 以此來改變起點的奇偶性，所以這個時候我們可以洗掉堆疊頂的邊，也就是將奇數點轉移，（為什么堆疊頂的邊是可以的？因為最后一條邊一定是連接到起點的，跑歐拉回路最終要回到起點的嘛，）這樣我們最后只會剩下一條邊，
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
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/181740.html
標籤：其他
上一篇：PTA題目：順序表---插入結點