BOJ 15271 - 친구 팰린드롬2

BOJ 15272 - 친구 팰린드롬2

[ 분류 - 이분 매칭 ]

주의해야할 점은 하나밖에 없다. 바로 친한 친구더라도 동성이라면 춤을 추지 않는다는 것.

남자와 여자로 이분 그래프를 구성하고, 최대 매칭을 구한다. 구한 뒤, 로봇 댄스를 출 친구를 섭외할 수 있으면 +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;
}