동아리 홍보하기
면접 대비시간 제한2초메모리 제한256 MB
숲이 주어질 때 모든 정점이 선택되거나 선택된 정점과 인접하도록 하는 최소 정점 집합을 구한다.
문제
건덕이는 건국대학교의 프로그래밍 동아리 알프스(ALPS)를 홍보하려고 전봇대에 전단지를 붙이고 있다. 그런데 전단지를 붙이는 일도 만만치 않아서, 최소한의 전단지로 최고의 홍보 효과를 내고 싶어 한다.
전봇대와 전봇대 사이는 연결된 길로만 다닐 수 있다. 전단지는 전봇대에 붙이고, 전단지를 붙인 전봇대와 이웃한 전봇대까지 홍보 효과가 나타나며, 어떤 전봇대에서 출발하여 다른 길을 통해 다시 그 전봇대로 돌아올 수 있는 경로는 없다. 건덕이는 새이기 때문에 길과 상관없이 날아서 다른 전봇대에 전단지를 붙일 수 있다.
두 전봇대 사이에 연결된 길들이 주어질 때, 건덕이가 붙여야 하는 최소 전단지의 개수를 구해 보자.
입력
전봇대의 수 N, 길의 개수 M이 공백으로 구분돼 주어진다.
이어지는 M개의 줄에는 두 자연수 A, B가 주어진다. A번째 전봇대와 B번째 전봇대 사이에 길이 있음을 의미한다. (전봇대는 1부터 N까지 번호매김된다)
출력
모든 전봇대에서 홍보효과를 누릴 수 있도록 하는 데 필요한 전단지의 최소 개수를 출력한다.
제한
- 1 ≤ N ≤ 200,000
- 0 ≤ M ≤ N-1