집합 추가 문제 1 - 서로소집합

SW Expert Academy 문제
백준 문제

초기에 {1}, {2}, ... {n} 이 각각 n개의 집합을 이루고 있다.

여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

연산을 수행하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 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 이하의 자연수이며 같을 수도 있다.

[출력]

각 테스트 케이스마다 1로 시작하는 입력에 대해서 같은 집합에 속해있다면 1을, 아니면 0을 순서대로 한줄에 연속하여 출력한다.

from 2019.spring.datastructure.

집합 추가 문제 2 - 문자열 집합 판별

백준 9250

문제

집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하나라도 집합 S에 있으면 'YES'를 출력하고, 아무것도 없으면 'NO'를 출력한다.

예를 들어, 집합 S = {"www","woo","jun"} 일 때, "myungwoo"의 부분 문자열인 "woo" 가 집합 S에 있으므로 답은 'YES'이고, "hongjun"의 부분 문자열 "jun"이 집합 S에 있으므로 답은 'YES'이다. 하지만, "dooho"는 모든 부분 문자열이 집합 S에 없기 때문에 답은 'NO'이다.

입력

첫째 줄에 집합 S의 크기 N이 주어진다. (1 ≤ N ≤ 1000)
다음 N개 줄에 집합 S의 원소들이 주어진다. 이 문자열의 길이는 100을 넘지 않는다.
다음 줄에 답을 판별해야 하는 문자열의 개수 Q가 주어진다. (1 ≤ Q ≤ 1000)
다음 Q개 줄에 답을 판별해야 하는 문자열이 주어진다. 이 문자열의 길이는 10000을 넘지 않는다.
입력으로 주어지는 모든 문자열은 알파벳 소문자로만 이루어져 있다.

출력

Q개 줄에 각 문자열에 대한 답을 출력한다.

from 2019.spring.datastructure.