[C++]백준 - 1717번 문제

1717번: 집합의 표현 (acmicpc.net)

1717번: 집합의 표현

 

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) (tistory.com)

[알고리즘] 유니온 파인드 (Union-Find)

 

이제, 1로 시작하는 입력이 들어오면, A와 B가 유니온 관계인지만 확인하면 됩니다.

 

코드

---

#include <iostream>
using namespace std;

int *parent;
//부모 찾기
int find_parent(int target)
{
    if(target == parent[target]) return target;
    return parent[target] = find_parent(parent[target]);
    
}

//유니온 만들기
void set_union(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
    
    if(a != b)
    {
        parent[b] = a;
    }
}


int main() 
{
	int N, M;
	scanf("%d %d", &N, &M);
	parent = new int[N + 1];
	for(int i = 0; i < N + 1; i++) parent[i] = i;
	for(int i = 0; i < M; i++)
	{
	    int is_check, a, b;
	    scanf("%d %d %d", &is_check, &a, &b);
	    
	    if(!is_check) set_union(a, b);
	    else 
	    {
	        if(find_parent(a) == find_parent(b)) printf("YES\n");
	        else printf("NO\n");
	    }
	}

	delete[] parent;
	return 0;
}

 

그 외

---