BOJ 백준온라인져지 15562 네트워크 풀이

1. i -> j 로 도착하는것만 중요하다

2. 중간에 있던 내용들은 다 삭제해준다.

3. 감을 못잡겠어서 출제자의 정해를 보고 풀었다.

문제

우리의 회사에는 N개의 네트워크 시스템 S1, S2, ..., SN와 이들을 연결하는 M개의 네트워크들 W1, W2, ..., WM이 있다. 네트워크 시스템들은 우선순위가 있어 모든 네트워크는 우선순위가 높은 곳에서 낮은 곳으로만 전달된다. 즉, SA에서 SB로 전달되는 네트워크가 있다면 A < B 이다.

최근 이 네트워크 시스템이 너무 난잡해져 이를 정리하기로 했다. 이를 설명하자면, 시스템 SA, SB, SC에 대해서 SA에서 SB로 전달되는 네트워크와 SB에서 SC로 전달되는 네트워크가 있다면 이 둘을 합쳐 SA에서 SC로 전달되는 네트워크로 간략화하는 것이다. 이 방식으로 간략화를 반복해서 최대한 네트워크의 수를 줄이고자 한다. 이 때, 남은 네트워크의 수를 구하여라.

입력

첫 번째 줄에 N와 M이 주어진다. (1 ≤ N, M ≤ 106)

M줄 동안 두 숫자 Ai, Bi가 주어진다. 이는 Wi가 SAi와 SBi를 연결함을 뜻한다. (i = 1, 2, ..., M, 1 ≤ Ai < Bi ≤ N)

출력

최대한 간략화했을때 남은 네트워크의 수를 출력한다.