Einstein學畫畫

題目描述

Einstein 學起了畫畫。

此人比較懶~~，他希望用最少的筆畫畫出一張畫……

給定一個無向圖，包含 $n$ 個頂點（編號 $1～n$），$m$ 條邊，求最少用多少筆可以畫出圖中所有的邊。

輸入格式

第一行兩個整數 $n,m$。

接下來 $m$ 行，每行兩個數 $a,b$（$a\ne b$），表示 $a,b$ 兩點之間有一條邊相連。

一條邊不會被描述多次。

輸出格式

一個數，即問題的答案。

樣例 #1

樣例輸入 #1

5 5
2 3
2 4
2 5
3 4
4 5

樣例輸出 #1

1

提示

對于 $50\%$ 的數據，$n\le 50$，$m\le 100$。

對于 $100\%$ 的數據，$1\le n\le 1000$，$1\le m\le {10}^5$。

---

思路

歐拉通路：經過所有頂點且每條邊恰好經過一次的通路
歐拉回路：經過所有頂點且每條邊恰好經過一次的回路
歐拉圖：有歐拉回路的圖

根據歐拉圖判別定理，無向圖G具有歐拉回路當且僅當G是連通的且無奇度頂點。當沒有奇度定點時，該圖為歐拉圖，存在經過所有頂點且每條邊恰好經過一次的回路，可以一筆畫，直接輸出1。

無向圖G具有歐拉通路、但沒有歐拉回路，當且僅當G是連通的且有2個奇度頂點，其余頂點均為偶度數的，這2個奇度頂點是每條歐拉通路的端點。當奇度定點只有兩個時，也可以一筆畫。

無向圖奇度點的個數一定是偶數個，因為每加一條邊，總度數加2。每多兩個奇度點，筆畫數多1，所以輸出 odd / 2。

---

AC代碼

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e6 + 7;int n, m;
int d[N];
int odd;int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;d[a]++;d[b]++;}odd = 0;for (int i = 1; i <= n; i++) {if (d[i] % 2) {// 奇度頂點odd++;}}if (odd) {cout << odd / 2 << endl;} else {cout << 1 << endl;}return 0;
}