BOJ 29153 성게 밭

문제 링크입니다.

암수 구분하기

성게 밭을 각 정점이 성게이고 서로 맞닿은 성게끼리 간선으로 이은 그래프로 해석해 봅시다.

문제 조건에 의해 암컷 성게끼리, 수컷 성게끼리는 간선으로 연결되어 있지 않습니다. 즉 성게 간의 연결 관계 그래프는 이분 그래프입니다.

성게 찾기

성게의 중심은 차수가 3 이상입니다. 성게끼리 맞닿은 가시는 두 성게의 중심과 연결되어 있으므로 차수가 2이고, 나머지 가시는 차수가 1입니다. 따라서 각 정점의 차수를 이용해 그 정점이 성게의 중심인지, 두 정점을 잇는 가시인지 판별할 수 있습니다. 이를 이용해 성게 간의 연결 관계 그래프를 구성할 수 있습니다.

성게 채집하기

성게를 하나 고르면 직접 연결된 다른 성게를 고를 수 없게 됩니다. 따라서 문제를 이분 그래프의 최대 독립 집합늬 크기를 구하는 문제로 생각할 수 있습니다. 쾨니그의 정리에 의해, 이분 그래프의 최대 독립 집합의 크기는 전체 정점 수 - 최대 매칭 수임이 알려져 있으므로 이분 매칭을 이용해 답을 구할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int> graph_e[15150];
vector<set<int>> e(15150);
int star[15150], par[15150], idx;
bool vis[15150], c[15150];

void color(int now, bool col){
	c[now] = col;
	for(auto nxt : e[now]){
		if(vis[nxt]) continue;
		vis[nxt] = 1;
		color(nxt, !col);
	}
}

bool dfs(int now){
	for(auto nxt : e[now]){
		if(vis[nxt]) continue;
		vis[nxt] = 1;
		if(!par[nxt] || dfs(par[nxt])) return !!(par[nxt] = now);
	}
	return 0;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n, m; cin >> n >> m;
	while(m--){
		int u, v; cin >> u >> v;
		graph_e[u].push_back(v);
		graph_e[v].push_back(u);
	}
	for(int i = 1; i <= n; i++){
		if(graph_e[i].size() >= 3) star[i] = ++idx;
	}
	for(int i = 1; i <= n; i++){
		if(graph_e[i].size() == 2){
			if(star[graph_e[i][0]] && star[graph_e[i][1]]){
				e[star[graph_e[i][0]]].insert(star[graph_e[i][1]]);
				e[star[graph_e[i][1]]].insert(star[graph_e[i][0]]);			
			}
		}
	}
	for(int i = 1; i <= idx; i++){
		if(vis[i]) continue;
		vis[i] = 1;
		color(i, 0);
	}
	int ans = 0;
	for(int i = 1; i <= idx; i++){
		memset(vis, 0, sizeof(vis));
		vis[i] = 1;
		if(c[i]) ans += dfs(i);
	}
	cout << idx-ans;
}