HDU - 3018解题报告

题意简述

给出n个节点，m条边，问要想全部经过这m条边且每个边只经过一次至少需要多少条路径

分析

这个题实际上就是一笔画问题中的定理二：如果连通无向图 G 有 2k 个奇顶点，那么它可以用 k 笔画成，并且至少要用 k 笔画成
证明参见维基百科：zh.wikipedia.org/wiki/一笔画问题#一笔画定理
需要注意的是，在这个题中，他只关心能不能遍历这m条边而不关心全部遍历这N个节点，所以当边的条数为0时，我们应当输出0；如果把题意改一下，改成最少需要多少条路径恰好遍历完这N各节点，我们便需要考虑着N各节点中有一个或几个单独构成一个联通块的情况

实现

记录每个联通块有哪些元素有多种实现方式，我采用的是带权并查集。建一个vector的数组，初始化里面的值是它本身，当两个节点之间有一条边相连时，首先判断两个节点是否属于同一集合，如果不是则进行合并，把x的代表元变为y同时把x所在vector中的元素全部添加到y所在的vector当中。重复上述操作M次（因为有M条边）之后，每一个集合的代表元的所在的vector当中存储了这个集合的全部元素。此时我们可以直接应用一笔画定理的定理二

参考代码

参考代码仅供参考，请各位同学先独立实现代码

#include<stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

#define N 110000

int vis[N], pa[N], d[N], used[N];
vector<int> vec[N];

void init(int n) {
    for (int i = 0; i <= n; ++i) pa[i] = i;
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    memset(used, 0, sizeof(used));
    for (int i = 0; i <= n; ++i) vec[i].clear();
    for (int i = 0; i <= n; ++i) vec[i].push_back(i);
}

int findset(int x) {
    return pa[x] == x ? x : pa[x] = findset(pa[x]);
}

int main() {
    int n, m;
    while (scanf("%d%d",&n,&m) == 2) {
        init(n);

        while (m--) {
            int u, v;
            scanf("%d%d",&u, &v);
            d[u]++; d[v]++;
            used[u] = used[v] = 1;
            int x = findset(u);
            int y = findset(v);
            if (x != y) {  //union
                pa[x] = y;
                for (int i = 0; i < vec[x].size(); ++i) {
                    vec[y].push_back(vec[x][i]);
                }
            }
        }

        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) continue;  //如果没有边则忽略它
            int x = findset(i);
            if (!vis[x]) {
                int v = 0;
                for (int j = 0; j < vec[x].size(); ++j) {
                    int deg = d[vec[x][j]];
                    if (deg & 1) v++;
                }
                cnt += (v == 0 ? 1 : v / 2);
                vis[x] = 1;
            }
        }

        printf("%d\n",cnt);
    }
    return 0;
}