작업 그래프

자동차와 같이 아주 많은 수의 부품으로 이루어진 제품을 조립하는 작업은 그리 간단하지 않다. 부품들을 조립하여 중간 단계의 부속품을 만들고, 또 이들을 조립하여 다음 단계의 부속품을 만들고, 결국에는 완제품을 만들게 된다.

조립 작업을 효율적으로 수행하기 위해서 완제품을 조립하는 과제를 작업자 한 사람이 하루에 할 수 있는 소과제들로 나누기로 하였다. 소과제는 몇몇 개의 부품이나 부속품으로 다음 단계의 부속품 하나를 조립하는 것이다. 부품이나 부속품 하나를 손질해야 하는 경우도 있어서, 하나의 부품이나 부속품으로 다음 단계의 부속품을 만드는 경우도 있다. 그리고 소과제들 사이에는 독립적으로 수행할 수 있는 것도 있지만, 다른 소과제가 종료된 후에만 수행이 가능한 경우도 있다.

소과제를 정점으로 나타내고 어떤 소과제 [eqn: y]를 수행하기 위해서 다른 소과제 [eqn: x]에서 조립한 부속품을 사용하는 경우 [eqn: x]에서 [eqn: y]로 유향 에지를 두면 유향 그래프가 된다. 이 유향 그래프에는 당연히 사이클이 없어야 한다.

문제는 유향 그래프가 주어졌을 때, 그것이 유향 사이클을 가지고 있는지 아닌지를 알아보는 프로그램을 작성하는 것이다. 프로그램 이름은 job.cpp, 프로그램 설명 파일 이름은 job.hwp로 하고, 실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 input.txt이다. 첫째 줄에는 유향 그래프의 정점 수 [eqn: n]과 에지의 수 [eqn: m]이 빈칸을 사이에 두고 주어진다. [eqn: n]은 10,000 이하인 양의 정수이다. 정점은 1부터 [eqn: n]까지 번호가 붙어 있다. 둘째 줄부터 마지막 줄까지 [eqn: m]개의 줄에는 한 줄에 하나씩 유향 에지가 입력된다. [eqn: x]에서 [eqn: y]로 유향 에지가 있으면 [eqn: x] 다음에 [eqn: y]를 입력한다. [eqn: x], [eqn: y] 사이에는 빈칸이 하나 있다.

2003 가을학기 문제해결기법	문제 #3

출력 형식

출력 파일의 이름은 output.txt이다. 유향 사이클이 없는 경우는 첫째 줄에 ‘-1’만 출력한다. 유향 사이클이 있는 경우는 임의의 유향 사이클을 하나를 출력한다. 유향 사이클을 출력하기 위해서는 먼저 첫째 줄에 유향 사이클의 길이, 즉 사이클에 속하는 정점의 수를 출력하고, 둘째 줄에 유향 사이클에 속한 정점을 사이클을 따라가면서 출력한다. 이때 정점 번호가 작은 것부터 시작한다.

입력과 출력의 예

입력(input.txt)

6 7

2 3

1 2

5 4

4 6

3 4

4 2

5 6

출력(output.txt)

3

2 3 4