1319.连通网络的操作次数

链接：1319.连通网络的操作次数
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：用以太网线缆将  n  台计算机连接成一个网络，计算机的编号从  0  到  n-1。线缆用  connections  表示，其中  connections[i] = [a, b]  连接了计算机  a  和  b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。给你这个计算机网络的初始布线  connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回  -1 。

题解 1 - typescript

• 编辑时间：2021-01-23
• 执行用时：212ms
• 内存消耗：54.6MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function makeConnected(n: number, connections: number[][]): number {
  const uf = new UnionFind(n);
  let count = 0;
  for (const [c1, c2] of connections) {
    if (uf.same(c1, c2)) {
      count++;
    } else {
      uf.union(c1, c2);
    }
  }
  return uf.size - 1 <= count ? uf.size - 1 : -1;
}

题解 2 - typescript

• 编辑时间：2021-04-30
• 执行用时：192ms
• 内存消耗：53.8MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function makeConnected(n: number, connections: number[][]): number {
  let c = 0;
  const uf = new UnionFind(n);
  for (const [comp1, comp2] of connections) {
    if (uf.same(comp1, comp2)) cpp;
    else uf.union(comp1, comp2);
  }
  return c >= uf.size - 1 ? uf.size - 1 : -1;
}