길드 인원수 추적
골드 IV의견: 0
어느 온라인 게임에는 \(n\) 명의 플레이어가 있고, 처음에는 각자 자기 자신만으로 이루어진 길드에 속해 있다. 따라서 처음에는 길드가 정확히 \(n\) 개 존재한다.
게임이 진행되면서 다음 형태의 합병 명령 이 순서대로 \(q\) 번 주어진다.
1 a b: 플레이어 \(a\) 가 속한 길드와 플레이어 \(b\) 가 속한 길드를 하나로 합친다. (이미 같은 길드라면 아무 변화도 일어나지 않는다.)
각 합병 명령을 처리한 직후마다, 현재 가장 인원이 많은 길드의 최대 인원수 와 현재 존재하는 서로 다른 길드의 개수 를 한 줄에 두 정수로 출력하여라.
\(1 \le n \le 200{,}000\), \(1 \le q \le 300{,}000\), \(1 \le a, b \le n\)
첫째 줄에 플레이어 수 \(n\) 과 합병 명령의 수 \(q\) 가 주어진다. (\(1 \le n \le 200{,}000\), \(1 \le q \le 300{,}000\))
다음 \(q\) 개의 줄에는 각각 1 a b 형식의 합병 명령이 주어진다. (\(1 \le a, b \le n\))
각 합병 명령 직후마다 (가장 큰 길드의 인원수)와 (현재 길드 개수)를 공백으로 구분하여 한 줄에 하나씩, 총 \(q\) 줄을 출력한다.
5 4
1 1 2
1 3 4
1 2 3
1 2 5
2 4
2 3
4 2
5 1처음 길드 5개에서 1-2를 합치면 최대 2명·4개, 3-4 합치면 2명·3개, 2-3 합치면 \(\{1,2,3,4\}\) 로 4명·2개, 마지막에 5까지 합쳐 5명·1개가 된다.
3 3
1 1 2
1 2 1
1 2 3
2 2
2 2
3 11-2 합병으로 2명·2개, 다음 2-1은 이미 같은 길드라 변화 없이 2명·2개, 마지막 2-3으로 모두 합쳐져 3명·1개가 된다.
riseoj 작성
출처 Original
평가 및 의견
길드 인원수 추적
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
길드 인원수 추적