题意

给出n个点m条边的图 每次只能走两步 问最少加多少条边能完整遍历这个图

思路：

完整遍历首先要保证图联通 这是肯定的 计算联通块的个数 把这几个联通块连在一起就能保证图是联通的 加的边数是联通块个数-1 其次是要保证 每个点都能遍历到 容易想到奇环 如果一开始遍历不到的点 进入奇环后转一圈 就可以遍历到 那么只要判断有无奇环 如果没有的话 就在偶环上加一条边 就构成了奇环

代码

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

const int N = 1e5 + 5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double E = 2.7182818284590452353;

vector <int> e[N];
int vis[N];

bool flag = 1;

void dfs(int x){
    for(int i = 0;i < e[x].size();i ++){
        int to = e[x][i];
        if(vis[to] == -1){
            vis[to] = vis[x] ^ 1;
            dfs(to);
        }else if(vis[to] == vis[x]){
            flag = 0;
        }
    }
}

int main()
{
    int n,m;cin >> n >> m;

    for(int i = 0;i < m;i ++){
        int x,y;cin >> x >> y;
        e[x].pb(y);
        e[y].pb(x);
    }
    mes(vis,-1);
    int cnt = 0;

    for(int i = 1;i <= n;i ++){
        if(vis[i] == -1){
            ++ cnt ;
            vis[i] = 0;
            dfs(i);
        }
    }

    cout << cnt - 1 + flag << '\n';

    return 0;
}