Union-Find, also known as Disjoint Set Union (DSU), is a data structure designed to efficiently handle connectivity queries and union operations betwean elements. Its primary use is to determine if two elements belong to the same connected component or set.

Core Operations

1. Union (Join): Merges the sets containing two given elements.
2. Find (Root): Determines the representative (root) element of the set containing a given element. This is used to check connectivity.

Implementation Template in Go

Here is a standard implementation template to a Union-Find structure.

type UnionFind struct {
    Count   int
    parent  []int
}

// Initialize creates the parent array where each node is its own parent.
func (uf *UnionFind) Initialize() {
    uf.parent = make([]int, uf.Count)
    for i := 0; i < uf.Count; i++ {
        uf.parent[i] = i
    }
}

// Find locates the root parent of a node with path compression.
func (uf *UnionFind) Find(node int) int {
    if node == uf.parent[node] {
        return node
    }
    // Path compression: flatten the tree during find
    uf.parent[node] = uf.Find(uf.parent[node])
    return uf.parent[node]
}

// Connected checks if two nodes share the same root.
func (uf *UnionFind) Connected(x, y int) bool {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    return rootX == rootY
}

// Union connects the sets containing nodes x and y.
func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX == rootY {
        return // Already connected
    }
    uf.parent[rootY] = rootX // Attach rootY's tree under rootX
}

Practical Applications

1. Path Existence Check

This problem involves determining if a path exists between two nodes in a graph after processing a series of connections.

package main

import "fmt"

func main() {
    var nodeCount, edgeCount int
    fmt.Scan(&nodeCount, &edgeCount)

    uf := UnionFind{Count: nodeCount + 1} // 1-indexed nodes
    uf.Initialize()

    var a, b int
    for i := 0; i < edgeCount; i++ {
        fmt.Scan(&a, &b)
        uf.Union(a, b)
    }

    var queryA, queryB int
    fmt.Scan(&queryA, &queryB)

    if uf.Connected(queryA, queryB) {
        fmt.Println(1)
    } else {
        fmt.Println(0)
    }
}
// UnionFind struct and methods as defined in the template above.

2. Redundant Connection in an Undirected Graph

Given a graph that became a tree with one extra edge added, find an edge that can be removed to restore the tree structure.

package main

import "fmt"

func main() {
    var edgeCount int
    fmt.Scan(&edgeCount)

    uf := UnionFind{Count: edgeCount + 1}
    uf.Initialize()

    var src, dest int
    for i := 0; i < edgeCount; i++ {
        fmt.Scan(&src, &dest)
        // If already connected, this is the redundant edge
        if uf.Connected(src, dest) {
            fmt.Printf("%d %d\n", src, dest)
            return
        }
        uf.Union(src, dest)
    }
}
// UnionFind struct and methods as defined in the template above.

3. Redundant Connection in a Directed Graph (Harder)

This problem deals with a directed graph where one additional edge creates either a cycle or a node with two parents. The goal is to find the correct edge to remove.

package main

import "fmt"

func main() {
    var N int
    fmt.Scan(&N)
    edges := make([][2]int, N)
    inDegree := make([]int, N+1)

    for i := 0; i < N; i++ {
        fmt.Scan(&edges[i][0], &edges[i][1])
        inDegree[edges[i][1]]++
    }

    // Case 1: A node has two parents (in-degree 2)
    candidateEdges := []int{}
    for i := N - 1; i >= 0; i-- {
        if inDegree[edges[i][1]] == 2 {
            candidateEdges = append(candidateEdges, i)
        }
    }
    if len(candidateEdges) > 0 {
        // Try removing the later edge first (candidateEdges[0] due to reverse iteration)
        if formsValidTree(edges, candidateEdges[0]) {
            fmt.Println(edges[candidateEdges[0]][0], edges[candidateEdges[0]][1])
        } else {
            fmt.Println(edges[candidateEdges[1]][0], edges[candidateEdges[1]][1])
        }
        return
    }

    // Case 2: No in-degree 2, meaning there is a directed cycle.
    findCycleEdge(edges)
}

// formsValidTree checks if the graph becomes a valid tree after removing a specific edge.
func formsValidTree(edges [][2]int, skipIndex int) bool {
    uf := UnionFind{Count: len(edges) + 1}
    uf.Initialize()
    for i, e := range edges {
        if i == skipIndex {
            continue
        }
        if uf.Connected(e[0], e[1]) {
            return false // Cycle detected
        }
        uf.Union(e[0], e[1])
    }
    return true
}

// findCycleEdge identifies the edge that creates a cycle in the graph.
func findCycleEdge(edges [][2]int) {
    uf := UnionFind{Count: len(edges) + 1}
    uf.Initialize()
    for _, e := range edges {
        if uf.Connected(e[0], e[1]) {
            fmt.Println(e[0], e[1])
            return
        }
        uf.Union(e[0], e[1])
    }
}
// UnionFind struct and methods as defined in the template above.