유니온 파인드는 각 원소가 부모를 가리키게 해 집합을 표현합니다. find는 부모를 따라 대표 노드를 찾고 union은 두 대표를 연결합니다.
경로 압축은 find 중 지나온 노드를 대표에 직접 붙여 다음 조회를 짧게 만듭니다. 집합 크기나 랭크에 따른 합치기와 함께 쓰면 반복 연산이 효율적입니다.
언제 쓰나
연결 요소, 네트워크 묶음, 간선 추가 시 순환 여부를 판단할 때 씁니다.
유니온 파인드
Union-find
서로소 집합을 합치고 같은 집합인지 대표 노드로 확인합니다.
···
<div class="v"><header><b>UNION–FIND</b><span id="state"></span></header><main><div class="nodes" id="nodes"></div><div class="path" id="path"></div></main><footer>path compression shortens find</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .nodes{height:55%;display:flex;justify-content:space-around;align-items:center}.nodes b{width:30px;height:30px;border:1px solid var(--line);border-radius:50%;display:grid;place-items:center;font:700 .9em ui-monospace,monospace}.path{text-align:center;color:var(--accent);font:600 .9em ui-monospace,monospace;white-space:nowrap}let n=0;const paths=["D → C → B → A","D → A","A is representative"];function draw(){document.getElementById("nodes").innerHTML=["A","B","C","D"].map((v,i)=>"<b class=\""+(i===3||i===0?"active":"")+"\">"+v+"</b>").join("");document.getElementById("path").textContent=paths[n];document.getElementById("state").textContent=["find(D)","compress","next find"][n];n=(n+1)%3}draw();setInterval(draw,1150)