Union-find2 [백준] 1717번, 집합의 표현 | (python,파이썬) 문제 링크 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 문제해결하기 기본적인 Union-Find 문제로, Union-Find를 이해했다면 쉽게 풀 수있는 문제이다. 개념정리 보러가기 ↓ [개념정리] 유니온 파인드(Union-Find) by "union by rank"| (python, 파이썬) 유니온 파인드(Union-Find) 알고리즘이란 ? ▷유니온 파인드는 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. → "합집합 판.. 2021. 7. 25. [개념정리] 유니온 파인드(Union-Find) by "union by rank"| (python, 파이썬) 유니온 파인드(Union-Find) 알고리즘이란 ? ▷유니온 파인드는 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. → "합집합 판별" 이라고 생각하면 편할 거 같다 ! ▷이는 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. ▷새로운 집합을 생성하는 make_set 연산 노드를 합치는 union 연산과 노드의 루트 노드를 찾는 find 연산으로 이루어진다. ▷생성된 노드의 부모 노드는 자기 자신이다. ▷rank는 union을 할때, 두 집합에 대한 부모, 자식 관계를 결정할때 사용한다.(시간 단축을 위함) → 트리의 높이라고 생각하면 될 거 같다. 노드 Class class Node : def __init__(self,key): self.key.. 2021. 7. 21. 이전 1 다음
