득이공간

[백준 C++] 1717 집합의 표현 - 분리집합 본문

PS/알고리즘 문제풀이

[백준 C++] 1717 집합의 표현 - 분리집합

쟁득 2024. 2. 1. 16:04
 

1717번: 집합의 표현

초기에 n+1개의 집합 {0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작

www.acmicpc.net

cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> RootNode;

int Find(int Node)
{
‌if (Node == RootNode[Node])
‌{
‌‌return Node;
‌}

‌return RootNode[Node] = Find(RootNode[Node]);
}

void Union(int NodeA, int NodeB)
{
‌int RootNodeA = Find(NodeA);
‌int RootNodeB = Find(NodeB);

‌int MinRootNode = min(RootNodeA, RootNodeB);
‌RootNode[RootNodeA] = MinRootNode;
‌RootNode[RootNodeB] = MinRootNode;
}

bool Determine(int NodeA, int NodeB)
{
‌return (Find(NodeA) == Find(NodeB));
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(NULL);
‌cout.tie(NULL);

‌int N, M;
‌cin >> N >> M;

‌RootNode.reserve(N + 1);
‌for (int i = 0; i < N + 1; ++i)
‌{
‌‌RootNode.emplace_back(i);
‌}

‌for (int i = 0; i < M; ++i)
‌{
‌‌int Option, A, B;
‌‌cin >> Option >> A >> B;

‌‌if (Option == 0)
‌‌{
‌‌‌Union(A, B);
‌‌‌continue;
‌‌}

‌‌if (Determine(A, B))
‌‌{
‌‌‌cout << "YES" << '\n';
‌‌}
‌‌else
‌‌{
‌‌‌cout << "NO" << '\n';
‌‌}
‌}
}

유니온 파인드 알고리즘을 사용해서 풀었습니다.

 

유니온 연산에서 집합을 합칠 때

해당 노드의 루트값을 변경하는 것이 아니라

루트 노드의 루트값을 변경해주는 것이 중요합니다.

'PS > 알고리즘 문제풀이' 카테고리의 다른 글

[백준 C++] 2252 줄 세우기 - 위상정렬  (0) 2024.02.01
[백준 C++] 1976 여행 가자 - 분리집합  (0) 2024.02.01
[백준 C++] 13549 숨바꼭질 3 - 다익스트라  (0) 2024.01.31
[백준 C++] 1916 최소비용 구하기 - 다익스트라  (0) 2024.01.31
[백준 C++] 1753 최단경로 - 다익스트라  (0) 2024.01.31
'PS/알고리즘 문제풀이' Related Articles more