버스 노선 > 문제은행

본문 바로가기


문제은행

2796 : 버스 노선

제한시간: 2Sec    메모리제한: 64mb
해결횟수: 211회    시도횟수: 1082회   



국경을 따라 순환 도로를 건설한 국가가 있다. 이 순환 도로에는 N 개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1 까지 번호가 시계방향 순서로 지정되어 있다. 현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다.

 

각 버스 노선은 [a, b]로 표시된다. 이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 순환도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

 

국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 예를 들어, N = 10 일 때, 5개의 버스 노선이 다음과 같이 있다고 하자.

 

[0, 4], [2, 6], [5, 0], [7, 9], [9, 4]

 

6218530a035dcddf80d1110aca065469_1454059 

위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 따라서 취소되는 버스 노선은 ①과 ④이다.

 

버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오.


입력의 첫 번째 줄에는 버스 정류소의 개수 N ( 3 ≤ N ≤ 1,000,000,000 ) 이 주어지고 두 번째 줄에는 버스 노선의 수 M ( 2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1 부터 M 까지의 번호로 구분된다.

그 다음 M 개의 줄에는 1 번 노선부터 순서대로 각 버스 노선 [a, b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다,
단, 0≤ a, b ≤ N-1 이고 a ≠ b 이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.

<제약조건>
• 부분문제 1: 전체 점수 100점 중 13점에 해당하며, M ≤ 5,000 이고, 입력으로 주어지는 모든 버스 노선 [a, b]에 대해 a 〈 b 이다.
• 부분문제 2: 전체 점수 100점 중 28점에 해당하며, M ≤ 5,000 이다.
• 부분문제 3: 전체 점수 100점 중 16점에 해당하며, 입력으로 주어지는 모든 버스 노선 [a, b]에 대해 a 〈 b 이다.
• 부분문제 4: 전체 점수 100점 중 43점에 해당하며, 원래의 제약조건 이외의 아무 제약 조건이 없다.


입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다.

[Copy]
10
5
0 4
2 6
5 0
7 9
9 4
[Copy]
2 3 5


[Copy]
20
4
14 17
18 3
8 6
9 13
[Copy]
3




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.