13503번 - 최소 체인 커버

그래프에서 체인이란 연속된 두 정점을 연결하는 간선이 존재하는 정점들의 나열이다. 이때 한 정점이 여러 번 등장할 수도 있으며, 정점 하나도 체인이다.

사이클이 없는 방향 그래프가 주어질 때, 모든 정점을 포함시키기 위해서는 최소 몇 개의 체인이 필요한지 구하여라.

서로 다른 두 체인 간에 정점을 공유할 수 없다.

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 10,000)과 간선의 개수 M (0 ≤ M ≤ 100,000)이 주어진다.

둘째 줄부터 M개의 줄에 간선의 정보 u, v가 주어지며, u에서 v로 가는 간선이라는 의미이다.

입력으로 주어지는 그래프는 사이클이 없는 방향 그래프이다.

모든 정점을 포함시키기 위해서는 필요한 체인 개수의 최솟값을 출력한다.

예제: 2->7->3->6, 1->5->4