【每日一题】 图的遍历 (dfs / 染色+判奇环)

Solution
题意:
无向图有n个点，从点1开始遍历，每次走两步，遍历整个图。
问最少加几条边，可以完整的遍历整个图。

思路：
首先可以想到的是如果图不连通，那么答案至少需要 (联通块的数目-1) 来把各个联通块连起来。
而走两步的话，不难联想到奇偶形，考虑奇环的话两步可以到达环内任意一点，所以只要连通后的图有奇环存在，那么答案就是 (联通块的数目-1) ， 否则需要多一条边来构造奇环，则答案为 (联通块的数目)。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=2e3+5;
const int mod=1e9+7;

vector<ll>g[manx];
ll col[manx];
ll flag=1;

void dfs(ll u,ll pre){
    for(auto v: g[u]){
        if(v==pre) continue;
        if(col[v]==-1){
            col[v]=col[u]^1;
            dfs(v,u);
        }
        else if(col[v]==col[u]) flag=0;
    }
}

int main(){
    ll n,m; cin>>n>>m;
    for(int i=1;i<=m;i++){
        ll u,v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    for(int i=1;i<=n;i++) col[i]=-1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(col[i]!=-1) continue;
        col[i]=0;
        dfs(i,0);
        ans++;
    }
    if(!flag) ans--;
    cout<<ans;
    return 0;
}