문제
제가 이해하기로는 이 문제는 minimum strongly connected subgraph(모든 vertex에서 다른 모든
vertex로의 길이 존재하고 arc들의 합이 최소가 되는 subgraph)를 찾는 문제 같은데요....(잘못 이해 하고 있으면
제대로 알려주시면 감사하겠습니다;;)
제가 알기로는 NP-hard로 알고 있어 일단 모든 M개의 arc중에서 vertex개수 N개, N+1, N+2...의 arc들의
순열을 골라 각각의 순열마다 해당 순열을 사용했을 때 strongly connected가 되는지 확인 하는 식으로
접근해보았는데요;; 별도의 prunning이나 아니면 다른 접근 방식이 필요해 보여서 질문드리게 됬습니다.
이런 문제는 어떤 식으로 접근 해야 할지 설명해주시면 감사드리겠습니다.