티스토리 뷰

ICPC/2014 대전

D. Exploration

전명우 2014.11.09 14:14

정점의 개수가 $N$개고 간선의 개수가 $M$개인 그래프가 주어진다. 각 정점의 차수가 $K$ 이상인 부분그래프 중 가장 큰 부분그래프의 크기를 구하는 문제다.


입력으로 주어진 그래프에서 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없으므로 제거한다. 그런 정점들을 제거하면 새로운 그래프가 나오는데, 마찬가지로 새로운 그래프에서도 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없다.


위와 같은 방법으로 더 이상 제거할 정점이 없을 때까지 정점들을 제거한다. 그 후 남은 그래프가 문제에서 요구하는 최대 크기의 부분그래프가 된다. 총 시간복잡도는 $O(M)$이 된다.


코드 보기


'ICPC > 2014 대전' 카테고리의 다른 글

G. Road Repair  (0) 2014.11.10
F. Permutation Cycles  (0) 2014.11.09
E. Marbles  (0) 2014.11.09
D. Exploration  (2) 2014.11.09
C. Eureka Theorem  (0) 2014.11.09
B. Deduction  (0) 2014.11.09
댓글
  • 프로필사진 비밀댓글입니다 2014.11.20 20:05
  • 프로필사진 전명우 댓글 달아주셔서 감사합니다.
    제 코드에서 오답을 내는 testcase가 있다는 말씀이신가요?
    대회 때 만점 받은 코드가 아니라 집에 와 새로 코딩한 코드인지라 틀린 부분이 있을 수 있습니다.
    입출력 데이터를 함께 올려주시면 확인해보겠습니다!
    2014.11.24 15:45 신고
댓글쓰기 폼