Find Connected Components with Quick Find

Quick-Find is an algorithm used to find connected components and detect cycles in a graph. Each element is initially assigned a unique ID, representing its set. When an edge connects two vertices, the algorithm merges their sets by assigning one of the IDs to both vertices and all other elements that shared their original IDs. This process ensures that all elements in a connected component share the same ID, making it easy to determine connectivity.

function find(ids, node) {
    return ids[node]
}

function union(ids, node1, node2) {
    if find(ids, node1) != find(ids, node2):
        for each index in ids:
            if ids[index] == find(ids, node2):
                ids[index] = find(ids, node1)
}

function quickFind(graph) {
    ids = [0, 1, 2, ..., n-1]
    for each edge (node1, node2) in graph.edges:
        union(ids, node1, node2)
    return ids
}