牛客小白月赛17 - 图的遍历

题目描述
小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\leq n\leq1e5, \ 2\leq m\leq 1e53≤n≤1e5, 2≤m≤1e5
1\leq u,v\leq n1≤u,v≤n
图中点的编号从1到n。

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

很明显就是判断奇环，如果有奇环，那么从奇环的任何一个点开始，都能到达奇环的所有点，所以我们对每个联通块来考虑即可。

如果某个联通块有奇环，那么我们只需要把所有的联通块连到一起即可，所以答案就是联通块个数减一。
如果不存在奇环，那么我们需要把奇数个联通块连到一起，再连向其他的偶联通块即可。所以答案就是联通块的个数。

怎么判断奇环：

求联通块个数很简单，dfs一遍即可。

找奇环，我们可以对联通块染色，染互相间隔的0,1，所以如果是偶数环，那么相邻的不会有相同的数字，否则为奇环。（二分图判定定理）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,cnt,flag,col[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa||col[to[i]]!=-1)	continue;
		col[to[i]]=col[x]^1;	dfs(to[i],x);
	}
}
signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	memset(col,-1,sizeof col);
	for(int i=1;i<=n;i++)	if(col[i]==-1)	cnt++,col[i]=1,dfs(i,0);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nex[j]){
			if(col[to[j]]==col[i])	return printf("%d\n",cnt-1),0;
		}
	}
	printf("%d\n",cnt);
	return 0;
}