https://ac.nowcoder.com/acm/problem/52275

题意：需要加多少条边才能使从1开始遍历整张图？

分析：
先从简单的问题进行考虑，假设每次都只能走1步，那么需要加多少条边才能遍历完呢，显然要把全部点都连通起来，因此需要加的边数就是（连通块的数量-1）条边。
如果每次只能走2步，在图刚好全部连通的基础上作图发现，无论从那个点出发都无法遍历全图，总会剩下一半的点遍历不到，某些点（偶数或者奇数点）给跳过去了，这种情况下我们加一条边形成奇数环可以把点转移到另一种性质的点上（奇数偶数转化），从而能遍历整张图了，不太明白的自己画图看看就知道了。
因此，只要我们发现，只要图连通且存在奇数环，那么便可遍历整张图，问题由此转化为求有多少个连通块和是否有奇数环。
而解决两种问题直接dfs染色便可以了，连通块之间染不同的颜色0和1，如果发现相邻点被染色了，且颜色与当前不同，说明有奇数环。

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int i,j,ans,n,k,m,x,y;
vector<int>v[100005];
int vis[100005];
int judge=1;
void dfs(int a,int b){//a表示当前点，b表示当前点颜色，用0和1表示
    for(auto &hi:v[a]){//遍历容器元素
        if(vis[hi]==-1){//没染色
            vis[hi]=b^1;//染成相反颜色
            dfs(hi,vis[hi]);
        }
        else if(vis[hi]==vis[a]){//相邻点被染色了，且颜色与当前不同，说明有奇数环
            judge=0;
        }   
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    memset(vis,-1,sizeof(vis));
    for(i=1;i<=n;i++){
        if(vis[i]==-1){//没染色
            ans++;
            vis[i]=0;
            dfs(i,0);
        }
    }
    printf("%d",ans+judge-1);
}