【每日一题】5月21日 图的遍历

题目大意:给定一张个点 条边的无向图，小sun可以选择一个起始点出发，每次行走都是夸两条边行走，问小sun要遍历所有点，需要添加多少条边.

分析:
题目没有说图一定连通，那么要遍历所有点肯定要使得图连通，那么要连通的加边数为：所有连通块的个数-1.
加完边后，图上所有点都是连通的.假如图上没有环，那么每次跨两条边行走，可以证明能行走的点是图上点的一半.那么如何也能走到另一半的点呢。
考虑图上有环，如果是偶环，举个例子:n=4,m=4,(1,2),(2,3),(3,4),(4,1).无论选择哪个点都只能走图上一半的点。
我们考虑奇环，举个简单例子:n=3 m=3 (1,2) (2,3) (3,1) .我们选取1号点作为起始点，可以到达3号点，从3号点出发可以到达2号点，2号点是1号点的相邻点，那么假如图中存在类似的奇环就可以遍历图上所有点.
那么可以得出只要图中是有奇环的连通块，那么就可以遍历所有点，如果不是奇环的话，我们可以选择一个点加一个自环边构成一个奇环.
那么最后加边数: 连通块个数-1 + ( 是否有奇环 ? 0 : 1 ) .
判断奇环常用方法 ： 二分图染色.

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

vector<int> g[maxn];
bool vis[maxn];
int col[maxn];
int flag=1;

void dfs( int x )
{
    vis[x]=1;
    for( int v:g[x] )
    {
        if( vis[v] )
        {
            if( col[x]==col[v] ) flag=0;
            continue;
        }
        col[v]=col[x]^1;
        dfs(v);
    }    
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for( int i=1;i<=m;i++ )
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans=0;
    dfs(1);
    for( int i=2;i<=n;i++ )
    {
        if( !vis[i] ) ans++,dfs(i); 
    }
    printf("%d\n",ans+flag);
}