Erdos & Gallai

최근에 UVa 모의고사를 참여했는데.. 문제가 비교적 쉬워서 3문제를 풀고..
마지막으로 D번을 풀려고했는데.. 문제가 도저히 이해가 안되서.. 그냥 포기하고 잤다..

문제는 11414 - Dream 인데.. 그냥 까먹고 있다가..
최근에 10720 - Graph Construction 문제를 우연히 보고나서.. 이게 같은문제란걸 파악.. -_-;;

문제 description을 어떻게 저렇게 엉망으로 써놓을수가 있는지.. 참내.. 내가 영어를 못하는건가.. 흑.. ㅠ_ㅠ;

이 문제는 Erdos & Gallai Theorem으로 해결할 수 있는데..
vertex의 개수와 각 vertex의 degree가 주어지고.. 이를 만족하는 simple graph를 그릴수 있는지 묻는 문제..
여기서의 simple graph는 undirect이고 self edge가 없고 같은 pair의 vertex를 연결하는 edge는 최대 하나이어야 한다..


참고자료:

invalid-file