图的遍历

题意：有一个n个点节点m条边的无向图，从点1开始遍历，按照每次“走两步”遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以最少加几条边，可以完整的遍历整个图？

思路：如果一个连通块中有奇数环，则该连通块可以全部遍历到，加一条边可以使二个连通块合在一起，最后在一个大于等于3的连通块中加一条边可以创造一个奇数环（如果没有奇数环），所以当有奇数环时答案为连通块的个数-1，否则为连通块的个数。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007

using namespace std;

vector<int>g[100005];
int ma[100005];

int dfs(int v,int k)
{
    ma[v]=k;
    int flag=0;
    for(int i=0; i<g[v].size(); i++)
    {
        if(ma[g[v][i]]==0)
        {
            flag=flag|dfs(g[v][i],k+1);
        }
        else
        {
            if((ma[v]-ma[g[v][i]])%2==0)
            {
                flag=1;
            }
        }
    }
    return flag;
}

int main()
{
    int n, m;
    scanf("%d %d",&n,&m);
    for(int i=0; i<m; i++)
    {
        int s, e;
        scanf("%d%d",&s,&e);
        g[s].push_back(e);
        g[e].push_back(s);
    }
    int z=0, flag=0;
    for(int i=1; i<=n; i++)
    {
        if(ma[i]==0)
        {
            flag=flag|dfs(i,0);
            z++;
        }
    }
    z=z-flag;
    cout << z << endl;
    return 0;
}