[BOJ] 3683 : 고양이와 개
3683 : 고양이와 개 풀이 이분그래프에서의 Maximum Independent Set(최대 독립 집합)을 구하는 문제이다. size(maximum independent set) + size(maximum matching) = size(vertices) 이거를 기억하자. 문제를 그래프화 시켜보자. 시청자를 노드, 의견 충돌을 엣지라고 두자. 시청자들은 cat을 남기고 dog를 떨어트리거나, dog를 남기고 cat을 떨어트리는 집단으로 나눌 수 있다. 그렇게 나눠서 엣지를 연결하면 이분그래프가 된다! 그런데 maximum independent set을 구하긴 힘드니까 위의 식을 정리해서, size(vertices) - size(maximum matching)를 구하자! 결국 이분매칭 문제가 되었다. 코드 #include <bits/stdc++.h> using namespace std;...