GRAPHCON은 어떻게 접근해야 할까요?

  • User Avatar
    restart

    그래프가 약해서ㅠㅠ 그래프 문제들을 좀 풀어보려고 했는데
    [[problem:GRAPHCON]]에서 바로 막혔네요..

    간단히 문제를 요약하면
    방향 그래프 G(V,E)가 주어지고, 이것의 connectivity를 유지하면서
    최대한 엣지수를 줄이는 문제인데요
    엣지에 대해 딱히 제한이 없는 걸 보면, loop도 가능해보이네요

    brute force로는 엣지를 하나하나 지워보고 해당 엣지의 initial vertex로부터 탐색을 돌려 connectivity가 변화하는지 알아보는 건데, 이건 O(N4)가 되네요ㅠㅠ.. 답이 나오는지도 확신이 안서구요..

    이런저런 연구를 해보면 N에 대해 답안 maximum은 2(N-1)일것 같은데
    0 0 0 1
    0 0 0 1
    0 0 0 1
    1 1 1 0
    과 같은 식으로 complete connectivity(?)를 만들 수 있어서요

    ㅜㅜ이런 문제는 어떻게 풀어야 할까요? 도움을 구합니다


    11년 전
4개의 댓글이 있습니다.
  • User Avatar
    kcm1700

    Strongly Connected Component로 분해한 뒤 생각해보세요.


    11년 전 link
  • User Avatar
    kcm1700

    SCC로 성분들 묶어주고 나면, Directed Acyclic Graph(DAG)가 되어요. DAG에서 풀어보세요.
    미리 처리를 해두면 edge마다 vertex를 하나씩 잡아보면서 체크할 수도 있어요.


    11년 전 link
  • User Avatar
    restart


    우와 감사합니다!!
    같은 SCC인 경우 각 SCC의 size만큼의 엣지를 쓰면 되고,
    나머지 DAG에서는 엣지를 tail은 topological order의 역순/ head는 topologocial order로 소트하여 O(V)의 connectivity를 체크하면서 필요없는걸 빼나가면 되겠네요! loop는 예외처리를 해줘야 될 것 같구요..ㅜㅜ


    11년 전 link
  • User Avatar
    restart

    AC받았습니다+_+ 감사합니다


    11년 전 link

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