Dogfootruler Kim

문제 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 유니온 파인드 문제이다. 유니온 파인드에 대해 이해가 가지 않는다면 , jainn.tistory.com/87 유니온 파인드(UNION-FIND) 파이썬 구현 유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 ..

유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용된다. 유니온 파인드(Union-Find)의 기능에 대해서 설명해보겠다. 1) Union : 두 집합을 하나의 집합으로 합치는 연산 2) Find : 어떤 원소 x가 주어졌을 때 이 원소가 속한 집합을 반환 위와 같이 두 가지 연산을 해주는 자료구조라고 할 수 있다. 정의를 알았다면 구현을 해보자 ! 구현 1. 초기화 parent 배열을 만들어준다. 파이썬 parent[a] = b #배열은 a 원소의 부모는 b이다. 라는 뜻으로 해석하면 된다. #초기화 시작 parent[i] = i ..