목록disjoint set (1)

Hello, Freakin world!

[백준 4195번] 친구 네트워크 - 상호 배타적 집합(disjoint set), 유니온 파인드

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 종만북의 유니온 파인드 코드를 참조한 풀이입니다. 주의할만한 몇 가지 포인트에 대해서만 짚고 가겠습니다. 1. 이름을 int형의 id값으로 변환 문자열로는 트리를 구성하기 불편하기 때문에 int형으로 변환했습니다. 2. find 연산에서의 경로 최적화 이는 중복 연산을 피하기 위해 트리의 구조를 수정하는 작업입니다. find를 수행할 때마다 루트를 찾음과 동시에 경로에 있는 노드의 parent를 모두..
알고리즘/자료구조 2020. 10. 27. 19:21
Prev 1 Next