Coxie   2년 전

다음과 같은 로직을 생각해 봤는데, 틀렸습니다가 뜹니다.

  1. 이미 비연결인 경우 0을 출력하고 종료한다. 1번 간선부터 dfs를 시작하여 모든 간선을 방문했는지 확인하는 방식으로 비연결인지 확인한다.
  2. 크루스칼 알고리즘을 이용하여 가중치 합이 최대인 트리를 만든다.

이 방법이 왜 틀렸을까요?

jh05013   2년 전

그래프 전체가 비연결이 되는 시점이 아니라 s와 t가 비연결이 되는 시점을 봐야 합니다.

댓글을 작성하려면 로그인해야 합니다.