题解:

假设图联通,那么由于每次走两步,相当于在规定一个起点后只能走奇偶性相同的点,所以,对于每一个连通块,我们只需要01染色后,看一下有没有相同颜色连边的情况,如果有,那就说明奇偶性不同的点能够到达,也就是说,我们可以遍历整张图,如果没有,那么我们直接加一条即可,
然后如果图不连通,那么首先,我们最少要多加连通块-1条边,然后如果这些连通块中有一个出现相同颜色边的情况,那么我们的只有把图联通即可,否则,则需多加一条


代码

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
    //freopen("a.in", "r", stdin);

    int n,m,col[100010],vis[100010],flag=1;
    vector<int> G[100010];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }

    function<void(int ,int)> dfs = [&] (int u,int cl) {
        col[u]=cl;vis[u]=1;
        for(int v:G[u]) {
            if(col[v]) {
                if(col[v]==cl) flag=0;
            }
            else dfs(v,3-cl);
        }
    };
    int t=0;

    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            dfs(i,1);
            t++;
        }
    }
    printf("%d\n",t-1+flag);

    return 0;
}

/*
8 8
1 2
2 3
3 4
4 2
5 6
6 7
7 8
8 6
*/