시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 123 | 28 | 16 | 32.000% |
안녕 친구들? 내 이름은 홍즈. 세계에서 제일 유명한 탐정이지. 요즘 내가 가는 곳마다 살인 사건이 끊이질 않아서 고민이야(웃음)! 서로에게 상처밖에 주지 못하는 불쌍한 사람들... 어쨋든 오늘도 나는 살인 사건을 찾아 헤매이고 있지. 돈을 벌어야 하니까.
나는 지금까지 탐정을 하면서 얻은 경험으로 사람이 일으키는 사건의 인과관계를 간단하게 압축할 수 있었어. 예를 들어 사건 A가 일어났다면 무조건 사건 B가 일어나야 한다는 것을 알고 있어. 이런 관계를 A → B라고 나타내자. 사건이 여러개 이어져서 A → B → C와 같은 관계가 있을 수도 있어, 하지만 A → B → C → ... → A 같은식으로 순환하는 관계는 없어. 그리고 만약 A → C이고 B → C라고 하고 사건 C가 일어났다고 하자. 이런 경우에는 사건 A나 사건 B중 하나는 일어났을거라는 사실을 알 수 있어.
오늘도 오늘의 살인 사건이 일어났군. 지금 증거들을 수집했어, 이걸로 나는 총 N개의 사건이 일어났다는 것을 알 수 있었어. 이것으로 나는 무조건 일어났을 다른 사건들이 더 있다는 사실을 알게 되었어. 나는 지성과 경험을 모두 겸비한 탐정이니까. 당신도 과연 알 수 있을까?
첫 번째 줄에 일어날 수 있는 사건의 개수 D (1 ≤ D ≤ 1000), 사건들 간의 관계의 개수 M (1 ≤ M ≤ 100000), 그리고 일어난 사건의 개수 N (1 ≤ N ≤ D)이 공백으로 구분되어 주어진다.
다음 M개의 줄에는 두 정수 A와 B(1 ≤ A, B ≤ D)가 주어지는데 이는 사건 A,B가 A → B인 관계에 있음을 나타낸다.
마지막으로 다음 N개의 줄에는 일어난 사건을 나타내는 정수 X (1 ≤ X ≤ D)가 주어진다.
무조건 일어나야 하는 사건을 한 줄에 공백으로 구분하여 출력한다. 순서는 상관없다.
3 2 1 1 2 2 3 2
1 2 3
3 2 1 1 3 2 3 3
3
4 4 1 1 2 1 3 2 4 3 4 4
1 2 3 4
사건 4가 일어났는데, 사건 {2,3}중에 어떤 사건이 4를 일으켰는지 알 수 없다. 그러나 사건 {2,3}이 일어나기 위해서는 사건 1이 일어나야 하므로, 홍즈는 어쨌든 사건 1이 일어났어야만 한다는 사실을 알 수 있고, 이로 인해서 사건 2,3,4도 일어났어야 한다는 사실을 알 수 있다.
Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #6 5번