15271 친구 팰린드롬 2

친하면서 이성인 친구와 춤을 출 수 있는 커플 수를 구하는게 요점이다.

남자, 여자로 나뉘고 친하다는 관계가 간선이므로 이분그래프가 성립한다.

이분매칭 돌리고 결과를 약간 손보면 된다.

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
const int MV = 200;
 
int n, m, ans, d[MV + 1];
bool c[MV + 1];
vector<int> a[MV + 1];
 
int dfs(int x) {
    if (x == -1) return 1;
    for (int i : a[x]) {
        if (c[i]) continue;
        c[i] = 1;
        if (dfs(d[i])) {
            d[i] = x;
            return 1;
        }
    }
    return 0;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (v % 2) swap(u, v);
        if ((u + v) % 2) a[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        memset(c, 0, sizeof(c));
        ans += dfs(i);
    }
    ans *= 2;
    if (ans != n) ans++;
    printf("%d", ans);
    return 0;
}