[Medium] GogoXMarisaKirisima

0번에서 도달할 수 없는 정점들을 모두 제거하고 n-1번으로 도달할 수 없는 정점들을 모두 제거하고 나면 (연결된 간선도 모두 제거) 답은 m - (n - 2) 다. 증명해보자. 1) 답의 상한은 m - (n - 2) 이다. 먼저 간단하게 생각해볼 수 있는건, 답은 무조건 m 이하라는 것이다. 매번 새로운 간선을 선택해야하기 때문에 간선 개수를 넘어서는 경로를 만들 수 없다. 현재 경로를 적당히 찾아놓은 상태라고 하자. 새로운 경로를 하나 찾을 것이다. 아직 방문하지 않은 점을 아무거나 하나 골라 u라고 하자. 0번에서 u까지 가는 경로는 무조건 존재하고 u에서 n-1로 가는 경로도 무조건 존재한다. 이제 0에서 u를 거쳐 n-1까지 가는 경로를 다음과 같이 잡자. 0 ----> a ----> u ----> b ----> n-1 * 0~>a 경로, b~>n-1 경로의 간선들은 전부 한번 방문한 간선이다. * a~>b 경로의 간선들은 전부 새로 방문하는 간선이다. * a~>b 경로는 단순경로다. 이렇게 되는 a~>b 를 항상 찾을 수 있다. 이 경로에 있는 점들은 전부 새로 방문하게 되는 정점들이다. 경로에 있는 점의 개수를 K라고 하면, 지난 간선의 개수는 K+1 개 이다. 이렇게 경로를 하나 찾게 되면, 새 경로를 한개 찾았지만 답이 될 수 있었던 K+1개의 '가능성' 들이 사라져버리게 된다. 따라서 답의 상한이 K만큼 줄어들게 된다. 이렇게 새 경로를 찾는 과정을 처음에 n-2개의 방문하지 않은 점이 있던 상태에서 모든 점을 방문할 때 까지 계속 반복할 수 있다. 다 방문하고 나면 답의 상한은 m - (n - 2) 가 된다. 2) m - (n - 2) 인 답이 존재한다. 위의 과정을 p번 반복해서 모든 정점과 모든 간선을 방문했다고 해보자. k[i] 는 i번 경로에서 새로이 방문하게 되는 정점의 수라고 하자. 우선 자명하게 k[1]+k[2]+...+k[p] = n-2 일 것이다. '방문하지 않은 간선 수' 는 매 단계마다 k[i]+1 개씩 줄어들 것이므로 p번 반복하고 나면 m-p-k[1]-k[2]-...-k[p] = 0 이고, 결국 p = m - (n-2) 가 된다. 따라서 m - (n - 2) 번 경로를 찾을 수 있다.