export type UnionFindGroupId = number;

export class UnionFindSet<T> {
  private id: UnionFindGroupId;
  private map: Map<T, UnionFindGroupId>;
  private mapRev: Map<UnionFindGroupId, Set<T>>;

  constructor() {
    this.id = 0;
    this.map = new Map();
    this.mapRev = new Map();
  }

  public find(v: T): UnionFindGroupId {
    if (this.map.has(v)) {
      return this.map.get(v)!;
    } else {
      this.map.set(v, ++this.id);
      this.mapRev.set(this.id, new Set([v]));
      return this.id;
    }
  }

  public union(a: T, b: T) {
    const aid = this.find(a);
    const bid = this.find(b);
    let aset = this.mapRev.get(aid)!;
    let bset = this.mapRev.get(bid)!;

    if (aset.size > bset.size) {
      for (const v of bset.values()) {
        this.map.set(v, aid);
        aset.add(v);
      }
      this.mapRev.delete(bid);
    } else {
      for (const v of aset.values()) {
        this.map.set(v, bid);
        bset.add(v);
      }
      this.mapRev.delete(aid);
    }
  }

  public isUnion(a: T, b: T): boolean {
    return this.find(a) === this.find(b);
  }
}

export class UnionFindArray {
  private data: number[];

  constructor() {
    this.data = [];
  }

  public find(v: number): number {
    if (this.data[v] === undefined) {
      this.data[v] = -1;
      return v;
    } else if (this.data[v] === -1) {
      return v;
    }

    return (this.data[v] = this.find(this.data[v]));
  }

  public union(a: number, b: number) {
    this.data[this.find(a)] = this.find(b);
  }

  public isUnion(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}