CF216B Forming Teams

并查集。
可以发现只有奇数环或者是偶数环才会影响到最终结果，因此出现奇数环我们踢掉一个人，出场人数为奇数也要踢掉一个人。因此我们考虑用并查集维护两个点之间的关系，如果他们位于同一个集合之中并且是一个奇数环，那么答案加一就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const int MAXN = 1100 ;
const int MAXM = 1100 ;
const int Inf = 0x7fffffff ;

int N, M, F[MAXN], Num[MAXN], Ans ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline int Find(int Now) {
    return (Now == F[Now]) ? F[Now] : F[Now] = Find(F[Now]) ;
}

inline void Union(int X, int Y) {
    int L1 = Find(X), L2 = Find(Y) ;
    if (L1 == L2) {
        if (Num[L1] % 2 == 1) 
            Ans ++ ;
    }
    else F[L1] = L2, Num[L2] += Num[L1] ;
}

int main() {
    N = Read() ; M = Read() ;
    for (int i = 1 ; i <= N ; i ++)
        F[i] = i, Num[i] = 1 ;
    for (int i = 1 ; i <= M ; i ++) {
        int A = Read(), B = Read() ;Union(A, B) ;
    }
    if ((N - Ans) % 2 == 1) Ans ++ ;
    printf("%d", Ans) ; return 0 ;
}