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

  • restart
    restart

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

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

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

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

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


    9년 전
4개의 댓글이 있습니다.
  • kcm1700
    kcm1700


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


    9년 전 link
  • kcm1700
    kcm1700


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


    9년 전 link
  • restart
    restart

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


    9년 전 link
  • restart
    restart

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


    9년 전 link

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