221124 문제 풀이 기록

P3 | 1523 - 종점

풀이 시간: 25분

시도 횟수: 1회

체감 난이도: ??

풀이 쓸 의향: 下

풀이

N이 충분히 작으므로, 모든 노드를 비트마스킹으로 종점이 아닌 노드들을 세자.

종점이 아닌 노드들만으로 서로를 연결할 수 있으며, 종점인 노드들은 모두 종점이 아닌 노드와 적어도 하나의 간선으로 연결되어 있으면 연결 그래프이고, 아니라면 연결 그래프가 아니다.

또한, 이미 연결 그래프인 경우에서는 어떻게 하더라도 종점 두 개는 반드시 만들 수 있으므로 정답의 최솟값은 2로 맞춰두면 편하다. (위 알고리즘으로 답이 2 미만으로 나오는건 n=2인 경우밖에 없으므로 별로 의미는 없긴 하다)

여담: 사실 난이도 플레 랜덤으로 슬쩍 가리고 풀었는데... 풀고 나서 이게 이 난이도가 맞나 싶었던 문제. 경험상 이런 생각이 들던 문제들은 보통 다른 사람이 기여했던게 맞았어서 난이도 기여에서는 손 뗐다.