每日一题：图的遍历

题意

无向图 $n$ 个点，每次必须跳两个，至少需要加多少条边可以遍历所有点。

solution

首先，如果图不联通，那么需要加联通分量 - 1 条边使图联通，然后发现一点，只要这个图存在奇数环，就一定能全部走完，不存在的话，随便加一条边生成奇数环即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, odd, x, y, res, vis[N], color[N];
vector<int> g[N];

void dfs(int u) {
  for (auto v : g[u]) {
    if (!vis[v]) {
      vis[v] = 1;
      color[v] = !color[u];
      dfs(v);
    } else if (color[u] == color[v])
      odd = 1;
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      res++;
      vis[i] = color[i] = 1;
      dfs(i);
    }
  }
  cout << res - odd << '\n';
  return 0;
}