// Naive Union-Find (no optimizations) — O(n) per operation in worst case
class UnionFindNaive {
  parent: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);  // each is its own parent
  }

  find(x: number): number {
    if (this.parent[x] !== x) return this.find(this.parent[x]);
    return x;  // root
  }

  union(x: number, y: number): void {
    const rx = this.find(x), ry = this.find(y);
    if (rx !== ry) this.parent[rx] = ry;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

find(x: number): number {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]);  // path compression
  }
  return this.parent[x];
}

class UnionFind {
  private parent: number[];
  private rank: number[];
  private components: number;  // number of disjoint sets

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank   = new Array(n).fill(0);
    this.components = n;
  }

  // Path compression — amortized O(α(n)) per call
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  // Union by rank — keeps trees balanced
  union(x: number, y: number): boolean {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;  // already in same set

    if (this.rank[rx] < this.rank[ry]) {
      this.parent[rx] = ry;
    } else if (this.rank[rx] > this.rank[ry]) {
      this.parent[ry] = rx;
    } else {
      this.parent[ry] = rx;
      this.rank[rx]++;  // tie: arbitrarily make rx root, increase rank
    }
    this.components--;
    return true;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }

  getComponents(): number {
    return this.components;
  }
}

const uf = new UnionFind(5);  // 5 elements: 0, 1, 2, 3, 4
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.connected(0, 2)); // true
console.log(uf.connected(0, 3)); // false
console.log(uf.getComponents()); // 2

// LeetCode 323 — Number of Connected Components in an Undirected Graph
function countComponents(n: number, edges: number[][]): number {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) {
    uf.union(u, v);
  }
  return uf.getComponents();
}

console.log(countComponents(5, [[0,1],[1,2],[3,4]]));  // 2
console.log(countComponents(5, [[0,1],[1,2],[2,3],[3,4]])); // 1

// LeetCode 684 — Redundant Connection
// Find the edge that, when removed, results in a tree (no cycles)
function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const uf = new UnionFind(n + 1);  // 1-indexed nodes
  for (const edge of edges) {
    const [u, v] = edge;
    if (!uf.union(u, v)) {
      return edge;  // union returns false → they were already connected → cycle
    }
  }
  return [];
}

console.log(findRedundantConnection([[1,2],[1,3],[2,3]]));  // [2,3]
console.log(findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]])); // [1,4]

// LeetCode 721 — Accounts Merge
// Group accounts by email — if two accounts share an email they belong to the same person
function accountsMerge(accounts: string[][]): string[][] {
  const emailToId  = new Map<string, number>();
  const emailToName = new Map<string, string>();
  let id = 0;

  // Assign a unique id to each email
  for (const acc of accounts) {
    const name = acc[0];
    for (let i = 1; i < acc.length; i++) {
      if (!emailToId.has(acc[i])) {
        emailToId.set(acc[i], id++);
        emailToName.set(acc[i], name);
      }
    }
  }

  const uf = new UnionFind(id);

  // Union emails within the same account
  for (const acc of accounts) {
    for (let i = 2; i < acc.length; i++) {
      uf.union(emailToId.get(acc[1])!, emailToId.get(acc[i])!);
    }
  }

  // Group emails by their root representative
  const groups = new Map<number, string[]>();
  for (const [email, eid] of emailToId) {
    const root = uf.find(eid);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root)!.push(email);
  }

  // Build result: name + sorted emails
  return Array.from(groups.values()).map(emails => {
    emails.sort();
    return [emailToName.get(emails[0])!, ...emails];
  });
}

// Kruskal's MST — O(E log E) due to edge sorting
function kruskalMST(n: number, edges: [number, number, number][]): number {
  // edges: [weight, u, v]
  edges.sort((a, b) => a[0] - b[0]);  // sort by weight
  const uf = new UnionFind(n);
  let mstWeight = 0;
  let edgesAdded = 0;

  for (const [w, u, v] of edges) {
    if (uf.union(u, v)) {      // add edge only if it doesn't form a cycle
      mstWeight += w;
      edgesAdded++;
      if (edgesAdded === n - 1) break;  // MST has exactly n-1 edges
    }
  }
  return mstWeight;
}

// Graph: 4 nodes, edges with weights
const edges: [number, number, number][] = [
  [1, 0, 1], [4, 0, 2], [3, 1, 2], [2, 1, 3], [5, 2, 3]
];
console.log(kruskalMST(4, edges)); // 6  (edges: 0-1 w=1, 1-3 w=2, 1-2 w=3)

// LeetCode 990 — Satisfiability of Equality Equations
function equationsPossible(equations: string[]): boolean {
  const uf = new UnionFind(26);  // one node per letter a-z
  const code = (c: string) => c.charCodeAt(0) - 97;

  // First pass: process all == equations
  for (const eq of equations) {
    if (eq[1] === '=') uf.union(code(eq[0]), code(eq[3]));
  }

  // Second pass: check != equations for contradictions
  for (const eq of equations) {
    if (eq[1] === '!' && uf.connected(code(eq[0]), code(eq[3]))) {
      return false;  // x==y and x!=y is a contradiction
    }
  }
  return true;
}

console.log(equationsPossible(["a==b","b!=a"])); // false
console.log(equationsPossible(["a==b","b==c","a==c"])); // true