boj (1) 썸네일형 리스트형 BOJ 16041. Double Clique 문제 링크 옛날에 나코더 셋에 있었던 문제인데, 풀이가 인상 깊어서 한 번 블로그에 남겨보려고 한다. 1. 문제 설명무방향 그래프 $G$가 주어진다. 정점들의 집합을 $V$라고 하자. $G$의 여그래프 $G'$을 다음과 같이 정의하는데, 모든 $a, b \in V \ (a \neq b)$ 에 대해서 $G$ 에서 $a, b$를 잇는 간선이 있다면 $G'$에는 간선이 없고, $G$ 에서 $a, b$를 잇는 간선이 없다면 $G'$ 에는 간선이 있다. 클리크는 모든 노드 쌍이 연결된 정점 부분 집합을 의미하는데,노드의 부분 집합 $S$ (공집합 포함)가 다음을 만족하면 더블 클리크 (Double clique)라고 정의한다.1. $S$는 $G$에서 클리크이다.2. $V-S$ ($S$를 제외한 나머지 노드 집합) .. 이전 1 다음
