2623. 음악프로그램

2623번: 음악프로그램

---

여러 개의 부분 순서가 주어진다. 우리의 목표는 모든 부분 순서를 만족시키는 전체 순서를 작성하는 것이다.

 

순서를 정해야 한다는 말에서 알 수 있듯이, 위상 정렬을 적용하면 된다.

위상 정렬을 수행하기 위해서는 그래프를 만들어야 한다. 우리는 주어진 입력으로부터 그래프를 쉽게 만들 수 있다.

 

예를 들어 예제 입력의 첫 번째 줄을 보자.

1 4 3

이 입력은 1→4, 4→3으로 쪼갤 수 있다. 그래프에서 간선을 추가하듯이 해 주면 된다.

 

이때 주의할 점은, 같은 순서가 여러번 입력될 수 있다. 예를 들어 다음의 입력이 주어졌을 때, 1→2는 한 번만 세야 한다. 그렇지 않으면 위상 정렬할 때 진입차수를 잘못 계산하게 된다.

2 2
2 1 2
2 1 2

---

mazassumnida

왜 골드 2인지 잘 모르겠다. 잘 쳐줘야 골드 3 정도 아닌가..

아무튼 이렇게 또 한 문제 풀어본다.