問題
오름차순 정렬의 경우 '<'(작음) 관계연산자를 통해서 다음과 같이 표현 할 수 있다. 정렬된 수열이 A,B,C,D라고 할 경우 A＜B, B＜C, C＜D인 경우를 뜻한다.
A＜B의 형태로 들어오는 정보에 따라 정렬된 순서를 출력하거나, 정렬할 수 없음을 출력하는 프로그램을 작성하라.
入力
입력은 수열의 원소의 개수 N(1≤N≤26)과 주어지는 원소들의 관계에 대한 정보의 개수 M이 주어진다. 원소의 관계는 X＜Y(X는 Y보다 작다.)와 같이 입력된다.
出力
입력에 대해 출력되는 경우는 정렬된 수열을 찾을 수 있을 때, 잘못된 관계가 주어 졌을 때, 정렬된 수열을 찾을 수 없을 때 3가지로 나누어서 출력하며, 각각의 경우는 아래와 같다.
Sorted sequence determined after # relations: 찾은 수열. Inconsistency found after # relations. Sorted sequence cannot be determined.
첫 번째 줄의 경우는 정렬된 수열을 찾을 수 있을 때, 두 번째 줄의 경우는 잘못된 관계가 주어졌을 때, 세 번째의 경우는 정렬된 수열을 찾을 수 없을 때를 뜻하며, #에는 각각의 경우가 결정되었을 때 까지 정보의 수가 들어가야 한다.
만약 어떤 단계에서 정렬 관계의 성립 여부를 알았을 때, 그 뒤의 관계는 고려하지 않는다.(설사 정렬 관계가 잘못된 데이터가 들어와도 이를 고려하지 않는다.)
例題 #1
4 6
A＜B
A＜C
B＜C
C＜D
B＜D
A＜B
Sorted sequence determined after 4 relations: ABCD.
例題 #2
3 2
A＜B
B＜A
Inconsistency found after 2 relations.
出典
East Central North America 2001
ログインしないとコードを書けません。