算法竞赛入门经典181页， 图的连通，欧拉路径
题目意思：
有n 座城市，每两个城市之间都有一条双向道路。现在给出 m 条道路，连接了若干城市，
现在要求，寻找任意一条路径，使得这条路径，经过这m条道路。
本题要点：
1、首先考虑图的连通问题：
假如该图有 block_num 个连通块， 每个连通块都存在欧拉路径，那么，只需要把这 block_num
个连通块，连起来即可。因此只需要添加 block_num - 1 条边（只有一点的连通块不考虑）。
某个连通块存在欧拉路径，说明这连通块，最多只有两点是奇度数的（假设为x, y点吧）。
连通块之间连线，就是奇数点之间连起来。
2、当某个连通块，不存在欧拉路径时候：
任意一个连通块的奇度数的点的个数，必然是偶数。 假设有 k 个奇度数点，
那么每两个奇度数点连线，最后留两个，一共需要连 (k - 2) / 2 条边。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 1010, MaxM = 1e6 + 10;
int head[MaxN], ver[MaxM], Next[MaxM];
int deg[MaxN];
int n, m, t, tot;
int block_id[MaxN]; //block_id[i] 表示点i属于哪个连通块编号
int block_num; //连通块数量
vector<int> v[MaxN]; //v[i] 表示连通块编号为i 的节点编号void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}void dfs(int x)
{
block_id[x] = block_num;v[block_num].push_back(x);for(int i = head[x]; i; i = Next[i]){
int y = ver[i];if(block_id[y] == false)dfs(y);}
}void solve()
{
block_num = 0;memset(block_id, 0, sizeof block_id);for(int i = 1; i <= n; ++i){
if(!block_id[i]){
block_num++;dfs(i);}}int have_edge_block = 0; //统计有边的连通块for(int i = 1; i <= block_num; ++i)if(v[i].size() > 1)++have_edge_block;int ans = m + have_edge_block - 1;for(int i = 1; i <= block_num; ++i){
int len = v[i].size(), odd_deg = 0;for(int j = 0; j < len; ++j){
if(deg[v[i][j]] & 1){
++odd_deg;}}if(odd_deg != 0)ans += (odd_deg - 2) / 2;}printf("%d\n", ans * t);for(int i = 0; i <= n; ++i){
v[i].clear();}
}int main()
{
int x, y, index = 0;while(scanf("%d%d%d", &n, &m, &t) != EOF){
if(0 == n && 0 == m && 0 == t)break;memset(deg, 0, sizeof deg);memset(head, 0, sizeof head);for(int i = 0; i < m; ++i){
scanf("%d%d", &x, &y);add(x, y);add(y, x);deg[x]++, deg[y]++;}printf("Case %d: ", ++index);if(0 == m){
printf("%d\n", 0);continue;}solve();}return 0;
}/* 5 3 1 1 2 1 3 4 5 4 4 1 1 2 1 4 2 3 3 4 0 0 0 *//* Case 1: 4 Case 2: 4 */