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

문제 링크 : www.acmicpc.net/problem/1717

 

 

응용없는 단순한 유니온 파인드(disjoint set)알고리즘이다. 

 

 

 

<전체적인 알고리즘>

1-1. type이 0이면 두 노드들의 root를 합친다.

      -> d배열에 각 노드들의 부모를 가리키도록 저장한다.(재귀로 끝까지 가보면 root가 나오게 됨)

1-2. type이 1이면 두 노드의 집합 여부를 출력한다. (root노드가 같으면 결국 같은 집합임)

 

 

 

<전체 코드>

#include<iostream>

using namespace std;

int d[1000002];

int find_root(int a)  //해당 집합의 root 찾아서 반환
{
	if (d[a] == a)return a;
	return find_root(d[a]);
}

void make_union(int a, int b)   //두 집합 하나로 합치기
{
	a = find_root(a);
	b = find_root(b);

	if (a < b)d[b] = a;
	else d[a] = b;
}

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++)
	{
		d[i] = i;
	}

	for (int i = 0; i < m; i++)
	{
		int type, n1, n2;
		cin >> type >> n1 >> n2;

		if (type == 0)
		{
			if (find_root(n1) != find_root(n2))make_union(n1, n2); //다른집합이면 합치기
		}
		else
		{
			if (find_root(n1) == find_root(n2))cout << "YES\n"; 
			else cout << "NO\n";
		}
	}

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.