链接：

文章目录

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题：

无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。

输入描述:
第一行两个整数n，m代表图的点数和边数。

接下来m行，每行两个整数u，v代表u，v有边相连（无向边）
输出描述:
输出一行，代表最少要添加的边数。
示例1
输入

5 4
1 2
2 3
3 4
4 5

输出

1

示例2
输入

5 5
1 2
2 3
3 4
4 5
1 5

输出

0

备注:
数据范围：
3≤n≤1e5, 2≤m≤1e5
1≤u,v≤n
图中点的编号从1到n。

走两步的意思：
比如现在有两条边：(1,2),(2,3)，从1开始走，只能走到1或者3。
(1->2->3),(1->2->1)

题解

首先，所有点都能到达，也就是图要连通，不连通的话走都走不到肯定不行，所以加边来连通它们。加边数就是现在存在的连通块的数量-1
都连通之后，每次两步两步的走，所走到的点都是偶数点，而奇数点无法走到，所以我们需要构造一个环，使得可以通过环从偶数点迈到奇数点，然后走的就全是奇数点了，这样全部都走完
注意，所连成的环如果是偶环，通过环走到的还是偶数，所以要构成奇环，把一个单独隔开剩下的不就成奇数了

总结下，答案就是连通块的个数+（0/1）
如果存在奇数环就加0，如果没有需要我们现构造，就加1
!((vis[v] - vis[u]) & 1)flag=0;
如果vis[v]-vis[u]的结果ans是偶数，ans&1就是0，！0=1，所以flag=0，也就是v到u的距离是偶数，再加上一个u到v的边就构成奇环，所以不用加一，表示flag=0

代码：

#include<bits/stdc++.h>
#include<bitset>
using namespace std;
typedef long long ll; 
const int maxn = 100007;
struct node {
   
    int v,next;
}edge[maxn*2];
int head[maxn],cnt;
bool flag = 1;
int vis[maxn];

 
void add(int u,int v) {
   
    
	edge[++cnt].v = v;
	
	edge[cnt].next = head[u];
	
	head[u] = cnt;
}

void dfs(int u,int fa) {
   
    vis[u] = vis[fa] + 1;
    for(int i = head[u];i;i = edge[i].next) 
	{
   
        int v ;
		v= edge[i].v;
		if(v == fa) continue;
        if(vis[v]) 
		{
   
            if(!((vis[v] - vis[u]) & 1) ) flag = 0;
            continue;
        }
        dfs(v,u);
    }
    return;
}
 
int main() {
   
 
    int n,m,ans = 0;
    cin>>n>>m;
    for(int i = 1;i <= m;++i) 
	{
   
        int u,v;
        cin>>u>>v;
        add(u,v);
		add(v,u);
    }
    
    for(int i = 1;i <= n;++i) 
	{
   
        if(vis[i]) continue;
        ans++;
        dfs(i,0);
    }
    cout<<ans - 1 + flag;
    return 0;
}