R00188
친구 무리의 크기
골드 IV레이팅
의견: 0
설명
어느 SNS에는 \(N\)명의 사용자가 있고, 처음에는 누구도 서로 친구가 아니다. 시간이 흐르며 다음 두 종류의 사건이 순서대로 발생한다.
C a b: 사용자 \(a\)와 \(b\)가 친구가 된다. (이미 친구였거나 같은 무리에 속해 있어도 무방하다.)S a: 사용자 \(a\)가 속한 친구 무리의 현재 인원 수를 출력한다.
친구 관계는 전이된다. 즉 \(a\)와 \(b\)가 친구이고 \(b\)와 \(c\)가 친구이면 셋은 같은 무리에 속한다. \(a = b\)인 C 사건이 들어올 수도 있는데, 이 경우 무리에는 아무 변화가 없다.
모든 S 사건에 대한 답을 차례대로 출력하여라.
제약
- \(1 \le N \le 200{,}000\)
- \(1 \le Q \le 200{,}000\)
- \(1 \le a, b \le N\)
입력 형식
첫째 줄에 사용자 수 \(N\)과 사건 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 사건이 주어지며, C a b 또는 S a 형식이다.
출력 형식
각 S 사건마다 해당 사용자가 속한 친구 무리의 인원 수를 한 줄에 하나씩 출력한다.
예제 1
입력
4 5
C 1 2
S 1
C 2 3
S 3
S 4
출력
2
3
1설명
\(1,2\)가 친구가 되어 무리 크기 \(2\). 이후 \(3\)도 합류해 \(\{1,2,3\}\) 크기 \(3\). \(4\)는 혼자이므로 \(1\).
예제 2
입력
2 5
C 1 1
S 1
C 1 2
C 1 2
S 2
출력
1
2설명
C 1 1은 변화 없음(크기 \(1\)). 같은 합병이 두 번 와도 무리는 \(\{1,2\}\)로 크기 \(2\).
문제 시리즈
골드 III문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
친구 무리의 크기
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
친구 무리의 크기
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기