学步园

B. Forming Teams

题意：要平均分配两只队伍，队伍内的人不能有敌对关系，一个人最多可以和两个人敌对，如果没办法按要求分配，那么输出最小要去掉的人数。

思路：因为一个人最多可以和两个人敌对，所以如果形成链或者是孤立的点都是可以分配的，如果形成偶数环，那么交错着安排也可以，只要判断奇数环就行，例如

1-2 2-3 3-1 必须要去掉一个人，最后去掉后的人如果是奇数的话，那么还得去掉一个人。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 102;
const int maxm = maxn*maxn;
struct edge{
    int v , nex;    
}e[maxm];
int k , head[maxn];
void addedge(int a , int b) {
    e[k].v = b;
    e[k].nex = head[a];
    head[a] = k++;   
}
int vis[maxn] , len , root;
bool flag;//判断是否有环 
void dfs(int u , int f) {
    if(flag) return;
    vis[u] = 1;
    len ++;
    for(int i = head[u] ; i != -1 ; i = e[i].nex) {
        int v = e[i].v;
        //printf("与u相连的是%d %d f = %d\n",v,vis[v],f);
        if(v == f) continue; //因为是无向边不用往回看
        if(vis[v] && v == root) {
            flag = 1;
            return;
        }
        dfs(v , u);  
    }  
}
int main() {
    int n , m , a , b , i;
    while(~scanf("%d%d",&n,&m)) {
        k = 0;
        memset(head , -1 , sizeof(head));
        while(m--) {
            scanf("%d%d",&a,&b);
            addedge(a , b);
            addedge(b , a);    
        }
        memset(vis , 0 , sizeof(vis));
        int ans = 0;
        for(i = 1 ; i <= n ; i ++) {
            if(vis[i]) continue;
            len = 0;flag = 0;
            root = i;
            dfs(i , -1);
            if((len&1) && flag) ans++; 
        }
        if((n - ans)&1) ans++;
        printf("%d\n",ans);
    }    
}