가톨릭대학교에 워터 슬라이드를??
면접 대비시간 제한1초메모리 제한1024 MB
방향 그래프가 주어질 때, 모든 정점을 덮도록 물을 붓는 시작 정점의 최소 개수를 구한다.
문제
치삼이는 축제를 맞아 가톨릭대학교에 건물 옥상에서 다른 건물 옥상으로 이동하는 워터 슬라이드를 짓기로 했다!
가톨릭대학교의 건물은 총 N개이고, 편의상 1번 건물부터 N번 건물까지 있다고 하자. 이 건물들의 옥상과 옥상 사이에 터널이 설치되어 있다면 터널을 따라 연결된 건물 옥상으로 물이 흐른다. 단 터널은 방향이 정해져 있어 주어진 방향으로만 물이 흐를 수 있으며, 이동할 수 있는 모든 건물 옥상으로 물이 흐른다. 예를 들어 1에서 2번으로 향하는 터널이 있고, 2에서 3번으로 향하는 터널이 있다면, 1번에 물을 붓는다면 2번과 3번 건물 옥상에도 물이 흘러간다는 의미이다. 또한, 두 옥상 사이의 터널이 여러 개가 있을 수 있으며, 하나의 건물 옥상에서 그 건물 옥상으로 연결되는 터널은 없다.
모든 터널은 설치가 완료되었고, 내일이 축제이므로 치삼이는 이제 양동이를 구입해 물을 흘려보내 워터 슬라이드를 완성하려고 한다! 하나의 양동이로는 하나의 건물 옥상에만 물을 부을 수 있고, 양동이는 상상할 수 없을 만큼 충분히 크기 때문에, 물을 부으면 터널을 타고 흐를 수 있는 모든 건물 옥상으로 전달된다. 하지만 양동이가 너무 비싼 관계로 치삼이는 양동이의 구매를 최소화하려고 한다.
여러분이 치삼이를 도와 최소 몇 개의 양동이로 모든 건물 옥상에 물을 흘려보낼 수 있는지 구해주자!
입력
두 정수 N (2 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100,000)이 주어진다. N은 건물의 개수를, M은 터널의 개수를 나타낸다. 건물 옥상들의 번호는 1과 N 사이의 정수다.
다음 M개의 줄에는 각각 두 정수 x, y (1 ≤ x, y ≤ N)가 주어지는데, 이는 x번 건물 옥상에서 y번 건물 옥상으로 향하는 터널이 설치되어있음을 뜻한다.
출력
모든 건물 옥상에 물을 흘려보내기 위해 최소한으로 필요한 양동이 개수를 출력한다.