주의해야할 점은 하나밖에 없다. 바로 친한 친구더라도 동성이라면 춤을 추지 않는다는 것.
남자와 여자로 이분 그래프를 구성하고, 최대 매칭을 구한다. 구한 뒤, 로봇 댄스를 출 친구를 섭외할 수 있으면 +1를 해준다.
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_V = 105;
vector<vector<int>> adj;
vector<int> bMatch;
bool visit[MAX_V];
bool dfs(int n) {
if (visit[n]) return 0;
visit[n] = 1;
for(int to : adj[n])
if (bMatch[to] == -1 || dfs(bMatch[to])) {
bMatch[to] = n;
return 1;
}
return 0;
}
int bipartiteMatching(int N) {
int res = 0;
bMatch = vector<int>(N/2, -1);
for (int i = 0; i < N / 2 + N%2; i++) {
memset(visit, 0, sizeof(visit));
if (dfs(i)) res += 1;
}
return res;
}
int main() {
int N, M,u,v;
scanf("%d%d", &N, &M);
adj = vector<vector<int>>(N/2 + N%2);
while (M--) {
scanf("%d%d", &u, &v);
u--, v--;
if (u % 2 == v % 2) continue; // 이성친구가 아님
if (!(u % 2)) adj[u/2].push_back(v/2);
else adj[v/2].push_back(u/2);
}
int tot = bipartiteMatching(N);
tot *= 2; // 매칭은 두 정점이 이어졌다는 것.
tot += N > tot ? 1 : 0; // 로봇댄스 출 친구 섭외
printf("%d", tot);
return 0;
}