-
[백준] 1717번 집합의 표현문제 풀이 2020. 8. 21. 18:43
1717 집합의 표현
문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.
출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
풀이)
Union-Find 방법으로 푸는 문제다.
집합의 부모를 저장하는 parent배열과 각 집합의 사이즈를 저장하는 s배열을 선언해서 이용했다.
코드)
1234567891011121314151617181920212223242526272829303132333435363738394041#include <stdio.h>#include <algorithm>using namespace std;int n, m;int parent[1000001];int s[1000001];int Find(int a) {if (parent[a] == a) return a;return parent[a] = Find(parent[a]); // 경로압축}void Union(int a, int b) {a = Find(a);b = Find(b);if (a == b) return;//이미 같은 집합이면 안합침//집합 큰 곳에다가 합침if (s[b] > s[a]) swap(a, b); //큰 곳을 a집합으로parent[b] = a;s[a] += s[b];}int main() {scanf("%d %d", &n, &m);for (int i = 0; i <= n; i++) {parent[i] = i;s[i] = 1;}for (int i = 0; i < m; i++) {int cal, a, b;scanf("%d %d %d", &cal, &a, &b);if (cal == 0) {//집합 a b를 합친다.Union(a, b);}else { //원소 a,b 같은집합?a = Find(a);b = Find(b);if (a == b) printf("YES\n");else printf("NO\n");}}return 0;}cs '문제 풀이' 카테고리의 다른 글
[백준] 4386번 별자리 만들기 (0) 2020.08.22 [백준] 1197번 최소 스패닝 트리 (0) 2020.08.22 [백준] 2263번 트리의 순회 (0) 2020.08.20 [백준] 13913번 숨바꼭질4 (0) 2020.08.19 [백준] 1167번 트리의 지름 (0) 2020.08.18