집합의 표현
골드 V의견: 0
초기에 \(n+1\)개의 집합 \(\{0\}, \{1\}, \{2\}, \dots, \{n\}\)이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
- \(1 \le n \le 10^6\)
- \(1 \le m \le 10^5\)
- \(0 \le a, b \le n\)
- 입력으로 주어지는 모든 값은 정수이다.
첫째 줄에 \(n\), \(m\)이 주어진다. \(m\)은 입력으로 주어지는 연산의 개수이다. 다음 \(m\)개의 줄에는 각각의 연산이 주어진다.
합집합은 0 a b의 형태로 입력이 주어진다. 이는 \(a\)가 포함되어 있는 집합과, \(b\)가 포함되어 있는 집합을 합친다는 의미이다.
두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 \(a\)와 \(b\)가 같은 집합에 포함되어 있는지를 확인하는 연산이다.
1로 시작하는 입력에 대해서 \(a\)와 \(b\)가 같은 집합에 포함되어 있으면 YES 또는 yes를, 그렇지 않다면 NO 또는 no를 한 줄에 하나씩 출력한다.
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1NO
NO
YES연산을 순서대로 처리한다.
- 0 1 3: \(1\)과 \(3\)을 합친다. 집합: \(\{1,3\}\).
- 1 1 7: \(1\)과 \(7\)은 다른 집합 → NO.
- 0 7 6: \(\{6,7\}\).
- 1 7 1: \(7\)(\(\{6,7\}\))과 \(1\)(\(\{1,3\}\))은 다른 집합 → NO.
- 0 3 7: \(\{1,3\}\)과 \(\{6,7\}\)을 합쳐 \(\{1,3,6,7\}\).
- 0 4 2, 0 1 1: 합집합(마지막은 자기 자신이라 변화 없음).
- 1 1 1: 같은 원소이므로 항상 같은 집합 → YES.
rip 작성
출처 지정되지 않음
평가 및 의견
집합의 표현
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
집합의 표현