백준 1717(집합의 표현) C++

집합의 표현 성공스페셜 저지

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

54515

17239

10451

28.467%

문제

초기에 {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 를 출력해도 된다)

예제 입력 1 복사

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 1

예제 출력 1 복사

NO
NO
YES

 

<코드>

#include<iostream>
using namespace std;
int parent[1000001];
int Find(int x) //집합뿌리를 찾아주고, 갱신하는 함수
{
	if (parent[x] == x) 
		return x;
	else return parent[x] = Find(parent[x]);
}
void Union(int x, int y) //x,y 서로 집합뿌리가 다르다면 합집합을 수행하는 함수
{
	x = Find(x);
	y = Find(y);
	if (x != y) parent[y] = x;
}
void Same_root(int x, int y) //x,y의 집합뿌리가 같은지 판단하는 함수
{
	x = Find(x);
	y = Find(y);
	if (x == y) 
		cout << "YES" << '\n';
	else 
		cout << "NO" << '\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i; 
	}
	for (int i = 0; i < m; i++) 
	{
		bool x;
		int y, z;
		cin >> x >> y >> z;
		if (!x) 
			Union(y, z);
		else 
			Same_root(y, z);
	}
	return 0;
}

 

<풀이>

앞에서 풀었던 1197(최소 스패닝 트리)와 원리는 거의 비슷했다. 유니온 파인드를 사용하는 문제이다. 

메인함수에서 x의 자료형을 int로 사용할때는 시간초과가 났는데, bool을 사용하니 시간초과가 안났다. bool이 시간을 절약해주는건지는 잘 모르겠다.