문제
오늘날 세상에는 다양한 종교가 존재하고, 어떤 종교에 속해 있는지를 추적하는 것은 어려운 일이다.
한 학교에는 총 n명의 학생이 있고, 처음에는 모든 학생이 각자의 종교를 가지고 있다.
하지만 시간이 지나며 학생들 사이에 영향을 주고받으며, 종교가 통합되기도 한다.
앞선 문제에서는 종교의 가짓수가 궁금했지만,
이번에는 각 종교를 몇 명이 믿고 있는 지가 궁금해졌다.
m 개의 작업을 수행하자. ( 입력 형식 참고 )
입력
정수 n, m 이 주어진다. ( 1 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000 )
이후 m 줄에 걸쳐 2가지 작업이 입력된다.
1 x y—x번학생과y번학생이 같은 종교를 믿게 된다. (같은 종교 집단으로 합친다)2 x— 현재까지,x번학생이 믿고 있는 종교를 함께 믿고 있는 학생은 총 몇 명인지 출력한다. ( x 번 학생도 당연히 포함한다. )
출력
2번 작업이 입력될 때마다 그에 맞는 결과를 출력한다.
예제1
5 7
2 2
1 1 2
2 2
1 3 4
1 2 3
1 1 4
2 3
1
2
4
처음에, 2번 학생의 종교는 2번 학생 혼자 믿고 있다. ( 답 1 )
다음에, 2번 학생의 종교는 1번 학생, 2번 학생이 믿고 있다. ( 답 2 )
마지막 작업을 할 시점에선, 1, 2, 3, 4 번 학생이 모두 같은 종교를 믿고 있다. ( 답 4 )
출처
@againalgo
로그인해야 코드를 작성할 수 있어요.