Union-find

유니온 파인드

Merge disjoint sets and compare representatives to test membership.

···
html
<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>
css
.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}
js
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)

Union-find represents each set with parent pointers. Find walks to a representative; union links two representatives.

Path compression connects visited nodes directly to the representative, shortening later lookups. Combined with union by size or rank, repeated operations are efficient.

When to use

Use it for connected components, grouping, and cycle checks while adding edges.

Open as page ↗