[題解]二分圖

a124. 二分圖

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define lld long long
#define N 100005
using namespace std;
int n,m,ans = 0,cnt[2];
vector<int> edge[N];

int color[N];

bool dfs(int cur,int c){
    color[cur] = c;
    cnt[c]+=1;
    bool flag = 1;
    for(auto i:edge[cur]){
        if(color[i]==color[cur])return 0;
        if(color[i]==-1)flag = (flag && dfs(i,!c));
    }
    return flag;
}

void solve(){
    memset(color,0,sizeof(color));
    
    for(int i=0;i<n;i++)color[i] = -1;
    
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;a--;b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        if(color[i]==-1){
            cnt[0] = 0;cnt[1] = 0;
            if(!dfs(i,0)){
                cout<<0<<endl;
                return;
            }
            ans += min(cnt[0],cnt[1]);
            //有可能是非連通圖，用+=
        }
    }
    cout<<ans<<endl;
}

signed main(){
    cin>>n>>m;
    solve();
}