Union-Find

class UnionFind {
  private parent: number[];
  private rank: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array<number>(size).fill(0);
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compression
    return this.parent[x];
  }
  /** Returns false when a and b were already in the same group. */
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra]; // union by rank
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    return true;
  }
}

function findRedundantConnection(edges: number[][]): number[] {
  const uf = new UnionFind(edges.length + 1);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b]; // union returns false → already connected
  }
  return [];
}

class UnionFind
  def initialize(size)
    @parent = Array.new(size) { |i| i }
    @rank = Array.new(size, 0)
  end

  def find(x)
    @parent[x] = find(@parent[x]) if @parent[x] != x # path compression
    @parent[x]
  end

  # Returns false when a and b were already in the same group.
  def union(a, b)
    ra = find(a)
    rb = find(b)
    return false if ra == rb

    ra, rb = rb, ra if @rank[ra] < @rank[rb] # union by rank
    @parent[rb] = ra
    @rank[ra] += 1 if @rank[ra] == @rank[rb]
    true
  end
end

def find_redundant_connection(edges)
  uf = UnionFind.new(edges.length + 1)
  edges.each do |a, b|
    return [a, b] unless uf.union(a, b) # already connected -> redundant
  end
  []
end