시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 814 159 121 29.369%

문제

때는 2118년….

세상의 모든 강과 호수가 말랐다..! 하지만 한 곳..! 인경호는 마르지 않았다. 심지어 지하에서 물이 계속 나왔다. 앞으로도 마르지 않을 것 이다.

인하대학교 학생들은 인경호의 물을 식수로 쓰기 위해 정수 시설을 설치 하기로 했다. 정수 시설은 인경호 안에 N개의 구역에 설치 되었다. 정수 시설이 있는 곳에서는 물을 마실 수 있다. 각 구역은 0번부터 N-1번까지 번호를 써놨다. 그리고 정수 시설에는 깨끗한 물만 흐르게 하기 위해 M개의 파이프를 이용해 연결 시켰다. 파이프로 연결된 정수 시설에서 물은 파이프를 통해 한 방향으로만 흐른다. 예를 들어 1번 정수 시설과 2번 정수 시설이 연결 되었다면 1번 정수 시설에서 2번 정수 시설로만 깨끗한 물이 흐르는 것 이다. 또한 2번 정수 시설과 3번 정수 시설이 연결되어 있다면 1번 정수 시설에서 3번 정수 시설로도 물이 흐른다. 이때 여러 개가 연결 될 수도 있고 하나도 연결 되지 않을 수 있다. 정수 시설을 설치했기 때문에 인하대학교 학생들은 목이 마를때면 모두 인경호의 물을 마신다. 인하대학교는 학생이 굉장히 많기 때문에 모든 정수 시설에서 최소한 1명은 물을 마신다.

100년 째 CTP 회장을 하고 있던 김세진은 이 소식을 듣고 엄청난 계획을 하기 시작했다..!

바로 세진 바이러스를 정수 시설에 넣는 것이다..! 세진 바이러스를 먹게 된다면 모두 다 김세진 처럼 변하게 된다..! 김세진의 목표는 인하대학교 학생들 모두에게 세진 바이러스를 감염 시키는 것이다..! 그러기 위해선 모든 정수 시설에 바이러스를 감염시켜야 하지만 세진 바이러스는 생산비가 굉장히 비싸다…! 바이러스는 물을 따라서 전염되기 때문에 세진이는 물이 흐르는 방향을 잘 파악하여 최소의 바이러스만 생산하려 한다.

이때 생산해야 할 바이러스는 몇 개인지 알아보자..!

입력

입력의 첫째 줄에 시설의 수 N(1 ≤ N ≤ 100000), 파이프의 수 M(1 ≤ M ≤ 100000)이 주어진다. 

이후 두 번째 줄부터 M+1번째 줄 까지  연결된 정수 시설  A(0 ≤ A ≤ N-1), B(0 ≤ B ≤ N-1) 가 주어진다. 만약 A B가 들어온다면 A에서 B로 흐르는 것을 의미한다. 동일한 파이프는 최대 한번만 들어온다. 

출력

세진이가 생산해야 할 최소의 바이러스 개수 K를 출력한다.

예제 입력 1

10 5
0 5
0 4
2 3
5 9
8 6

예제 출력 1

5

예제 입력 2

5 3
0 1
1 2
2 0

예제 출력 2

3

출처

University > 인하대학교 > 2018 인하대학교 프로그래밍 경진대회(IUPC) D번

  • 문제의 오타를 찾은 사람: njw1204
  • 데이터를 추가한 사람: rdd6584
  • 문제를 만든 사람: tpwls1213