시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1299 | 378 | 261 | 28.034% |
원이는 요즘 유행하는 게임을 하고 있다. 이 게임은 is 라는 단어를 이용해 어떤 사물을 다른 사물로 바꿀 수 있다. 규칙은 다음과 같다.
어떤 사물 p에 대해 적용할 수 있는 명령이 두 가지 이상이면, 그 중 아무거나 하나 골라서 적용할 수 있다. (아무 명령도 적용하지 않을 수도 있다.) 그리고 어떤 사물 p에 명령을 한 번 이상 적용한 결과로 다시 p가 나오는 경우는 없다.
게임 초기에 설정된 명령들이 주어졌을 때, Baba에 명령을 적용하여 어떤 사물로 만들 수 있는지 구해보자.
첫 줄에 전체 명령의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
이후 N개의 줄에 걸쳐 명령이 주어진다. 각 명령은 p is q의 형태로 주어지며, p와 q는 첫 글자가 영문 대문자이고, 나머지 글자는 영문 소문자인 길이 10 이내의 문자열이다.
Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다.
1 Rabbit is Carrot
적용할 수 있는 명령이 아예 없으므로, 아무것도 출력하지 않는다.
3 Rabbit is Carrot Baba is Cat Cat is Rabbit
Carrot Cat Rabbit
Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물은 Cat, Rabbit, 그리고 Carrot이다.
1 Baba is Rabbit
Rabbit
4 Baba is Rabbit Rabbit is Cat Cat is Wall Wall is Unist
Cat Rabbit Unist Wall
University > UNIST > 제 1회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE B번