아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

핵심 하위 프로젝트

시간 제한0.6초메모리 제한32 MB

요약
DAG에서 다른 모든 정점과 도달 가능성으로 비교되는 정점을 모두 찾는다.
난이도

보통10점 중 7점

유형
그래프, 위상 정렬, DFS
정답자
아직 제출이 없습니다

문제

큰 프로젝트 하나가 서로 다른 하위 프로젝트 NN개로 나뉘어 있다. 관리자는 하위 프로젝트 사이의 선후 관계를 정해 두었다. 하위 프로젝트 uu를 끝내야만 하위 프로젝트 vv를 시작할 수 있는 쌍 (u,v)(u, v)가 있고, 이때 uu가 vv에 직접 선행한다고 한다. uu가 vv에 직접 선행하거나, uu가 zz에 선행하고 zz가 vv에 선행하는 하위 프로젝트 zz가 있으면 uu가 vv에 선행한다고 한다.

uu를 제외한 모든 하위 프로젝트 vv에 대해 vv가 uu에 선행하거나 uu가 vv에 선행하면, 하위 프로젝트 uu를 핵심 하위 프로젝트라고 한다.

전체 프로젝트는 완료할 수 있다. 즉 자기 자신에게 선행하는 하위 프로젝트는 없다.

핵심 하위 프로젝트를 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 NN과 MM이 주어진다. NN (1≤N≤1000001 \le N \le 100000)은 하위 프로젝트의 개수이고, MM (0≤M≤10000000 \le M \le 1000000)은 직접 선행 쌍의 개수다. 하위 프로젝트는 11번부터 NN번까지의 번호로 구분한다. 이어지는 MM개 줄에는 각각 두 정수 uu와 vv (1≤u≠v≤N1 \le u \ne v \le N)가 주어지며, 이는 uu가 vv에 직접 선행한다는 뜻이다.

출력

첫째 줄에 핵심 하위 프로젝트의 개수를 출력한다. 둘째 줄에는 핵심 하위 프로젝트의 번호를 오름차순으로 출력하고, 번호 사이는 공백 하나로 구분한다. 핵심 하위 프로젝트가 하나도 없으면 첫째 줄에 00만 출력하고 끝낸다.

힌트

첫 번째 예제의 선후 관계를 나타낸 그림이다.

예제3

  1. 예제 1

    입력
    7 9
    1 3
    2 3
    3 4
    3 5
    4 6
    5 6
    1 7
    3 7
    7 4
    
    예상 출력
    2
    3 6
    
  2. 예제 2

    입력
    1 0
    
    예상 출력
    1
    1
    
  3. 예제 3

    입력
    2 0
    
    예상 출력
    0