ICPC 온라인 예선 D번문제 어떻게 풀었나여?

  • dgsquare
    dgsquare

    안녕하세요. 올해 ICPC 문제를 보는 도중 D 번 문제를 보게 되었는데요.
    나름대로 생각을 해보다가 풀이를 생각해 보았는데, 제 풀이가 맞는지도 모르겠고, 다른 분들의 풀이가 궁금해서요.

    제가 생각한 방법은, 
    1. 먼저 cycle을 제거한다. (DFS를 통해서 찾은다음, 이것을 하나의 vertex로 둔다.)
    2. 그럼, Tree형태로 나오게 되는데요.
    3. 다시 DFS를 통해서 순회하며 각 leaf노드를 찾는다.(루트 포함)
    최종적으로, 연결에 필요한 노드의 수는 
    (leaf node갯수 + 1) / 2 개 이고,
    단, 전체 node가 1개일 경우는 0을 리턴한다.
    대충 이렇게 생각은 해봤는데, 왠지 틀릴것 같다는 ㄷㄷㄷ..
    실제 예선에서 풀었던 분들이 어떻게 풀었는지 궁금하네요..
    아니면 고수님들의 해설 부탁드립니다... 꾸벅 _-_

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
3개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    맞습니다. 그대로 코딩하면 됩니다.


    16년 전 link
  • 김우현
    김우현

    저희팀 풀이는
    각각의 Biconnected Component를 하나의 노드로 하는 그래프를 만든 다음에
    (degree가 1일 노드 갯수+1)/2
    갯수를 출력했습니다.
    원리는 똑같은 것 같습니다.


    16년 전 link
  • dgsquare
    dgsquare

    그렇군여.. 답변 감사합니다! Idea가 틀리지는 않아서 기분이 좋네여 :D
    (우현님 풀이가 좀 더 정확한거 같네요.)
    그런데 이런문제는 코딩을 정확히 해줄 필요가 있을 것 같군요~!


    16년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.