union find

[Algorithm] Union Find (Disjoint Set Forest)

💡여러 개의 노드가 존재할 때 그 중 두 개의 노드를 선택해서 서로 같은 그래프에 존재하는지 판별하는 알고리즘정의Union Find는 크게 두 가지 명령으로 이루어집니다.Union(a, b) - 노드 a와 b를 간선으로 연결합니다.Connected(a, b) - 노드 a와 b를 연결하는 경로가 존재하는지 확인합니다. 활용되는 상황두 점 간 연결되었는지 확인하면서 간선을 계속 추가해보는 동적인 상◼︎ 그래프 전체가 미리 주어지고 형태가 변하지 않는 고정된 정적인 상황에서는 적절하지 않습니다.◼︎ 두 점 연결하는 최단 경로 찾는 것과는 다른 문제입니다.연결 상태를 조금씩 받아오는 동시에 연결 상태를 확인하는 상황 ex) 컴퓨터망에서 두 장비가 연결되었는지?비행기 노선도에서 임의의 두 지역이 연결되었는지? 구..