서로소 집합 검색 결과
2 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 1717번 집합의 표현(서로소 집합 자료구조)(Union-Find)(Python-파이썬)

백준 1717번 문제입니다. (solved.ac)기준 골드 4 문제 입니다. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 접근 0부터 n까지 n+1개의 숫자가 있고 {0, 1, ...n} 형식의 집합이 존재합니다. 여기에 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산을 수행하려고 한다고 합니다. 첫째 줄에 n과 m이 주어지는데 n은 집합을 구성하는 마지막 수(0~N까지)이고..

2022. 3. 8. 07:59
정보[Information]

서로소 집합 자료구조(Union-Find)(Python-파이썬)

서로소 집합(Disjoint Sets) 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1,2} 와 집합 {3,4}는 서로소 관계이다. 반면에 집합 {1,2}와 집합 {2,3}은 2라는 공통 원소가 있으므로 서로소 집합이 아니다. 서로소 집합(Disjoint Sets) 자료구조 / 합집합-찾기(Union-Find) 자료구조 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정한 원소가 속한..

2022. 3. 5. 18:27