Union Find 썸네일형 리스트형 1717 - 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 이 전에 풀었던 1976 - 여행 가자 문제와 유사한 문제입니다. 단, 이 문제는 중간 중간마다 결과를 출력해야 한다는 점만 분기를 .. 더보기 1976 - 여행 가자 MST (Minimum Spanning Tree, 최소신장트리)를 하려면 크루스칼 알고리즘이 필요합니다. 근데 크루스칼 알고리즘을 사용하기 위해선 Union Find라는 알고리즘이 또 필요합니다. 그렇다면 차근차근 Union Find부터 알아봅시다. Union Find란 서로가 속한 집합이 같은 집합인지 파악하는 것입니다. 즉, 학교 내의 학생 2명이 같은 반인지를 확인하는 알고리즘이라 생각하면 됩니다. Union Find를 구현하기 위해 배열과 Tree를 사용할 수 있지만, 본 글에서는 배열로 다루는 Union Find를 설명할 것입니다. Union Find를 구하기 위해선 총 3개의 행위(메소드)가 필요합니다. 우선 배열을 초기화하는 init과 각자의 Root를 구하기 위한 find, 서로 같은 Ro.. 더보기 이전 1 다음