문제1906--twitter.com

1906: twitter.com

실행시간 제한: 20 Sec  메모리사용 제한: 256 MB
제출: 840  통과: 194
[제출] [채점기록] [묻고답하기]

문제 설명

이번 과제는 현재 유행하는 SNS인 twitter.com 의 following system의 일부를 구현하는 과제다.
 
만약 임의의 사용자 X가 Y라는 사용자를 following 할 경우 사용자 X의 time-line(시간 순으로 글이 올라오는 장소) 에서는 Y가 올린 글을 볼 수 있다.
 
이번 과제는 총 N명의 twitter.com 사용자가 존재할 때, Q개의 명령을 처리하는 프로그램을 작성하는 것이다. 명령의 종류는 아래 Input의 설명을 참고하도록 한다.
 

입력 설명

입력의 첫줄에는 사용자의 수 N ( 1 ≤ N ≤ 1,000,000 ) 과 명령의 수 Q ( 1 ≤ Q ≤ 100,000 ) 가 입력된다.

 
명령은 두가지 종류로 다음과 같다.
  • F A B
    • F는 대문자 'F'이며 A와 B는 0이상 N-1 이하의 정수다.
    • 이는 A번 사용자가 B번 사용자를 following 한다는 의미다.
    • 자기 자신을 follow 하는 경우는 존재하지 않으며, 기존에 following을 하던 사람을 B에 입력 하는 경우는 존재하지 않는다.
  • U A B
    • U는 대문자 'U'이며 A와 B는 0이상 N-1 이하의 정수다.
    • 이는 A번 사용자가 B번 사용자를 더이상 following 하지 않는다(unfollowing)는 의미다.
    • 자기 자신을 unfollow 하는 경우는 존재하지 않으며, 기존에 following을 하지 않던 사람이 B에 입력하는 경우는 존재하지 않는다.
각 명령에 입력된 사용자 A가 follow 하는 사람들의 수와 명단을 출력해야한다. 만약 follow 하는 사용자의 수가 10명을 넘을 경우 수는 그대로 출력하고, 명단은 사용자 번호 기준 오름차순으로 정렬했을 때 10번째 사용자 까지 출력한다.
 
주의 : 1인당 following 할 수 있는 사람의 수는 최대 5000명이다. 그 이상의 수를 following 하는 경우는 입력으로 들어오지 않는다.
 

출력 설명

출력형식은 다음과 같다.

<X> M : A1,A2,...,AM
X는 follwing을 하거나 unfollowing을 하는 사용자를 뜻하며, M 은 follow 하고 있는 사람의 수를 뜻하며, A1, A2, ..., AM은 오름차순 기준으로 첫번째, 두번째, ..., M번째 사용자를 뜻한다.
만약 following 하는 사람이 하나도 없을 경우 <X> NONE을 출력한다.
 

입력 예시 Copy

3 6
F 1 2
F 0 1
F 0 2
U 0 1
U 0 2
F 1 0

출력 예시 Copy

<1> 1 : 2
<0> 1 : 1
<0> 2 : 1,2
<0> 1 : 2
<0> NONE
<1> 2 : 0,2

출처/분류