4465 - 위상정렬

• Submit
• Status
• Discuss
• Summary

Description

다음은 위키피디아의 위상정렬의 정의이다.

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 이 점에서 비순환 유향 그래프(directed acyclic graph) 이다.

비순환 유향 그래프와 문자열S이 주어졌을때 S가 위상정렬 되어 있는지 판단해 보자. 

Input

* Line 1 : 정점수V 에지수E 문자열수N

• 1 ≤ V ≤ 100
• 1 ≤ E ≤ 100,000
• 1 ≤ N ≤ 1000

* Line 2 ~ E+1 : V1 V2

• V1, V2 : 0~499 범위의 정수 

* Line E+2 ~ E+N+1 : 문자열S

• S : 주어지는 정점의 개수와 공백으로 구분된 정점. 정점은 중복해서 주어지지 않는다.

* V1에서 V2로 가는 에지는 최대 한 개이다.

Output

* Line 1 ~ N : Y or N

 - Y : 위상정렬되어 있음

 - N : 위상정렬되어 있지 않음

Sample Input

6 8 2
0 2
0 3
1 3
1 4
2 3
2 5
3 5
4 5
5 1 0 2 4 3
4 4 3 5 2

Sample Output

Y
N

Source

c자료구조10장