547.省份数量

链接：547.省份数量
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。返回矩阵中 省份 的数量。

题解 1 - typescript

• 编辑时间：2021-01-07
• 执行用时：92ms
• 内存消耗：41.1MB
• 编程语言：typescript
• 解法介绍：深度优先搜索。

function findCircleNum(isConnected: number[][]): number {
  const set = new Set<number>();
  let ans = 0;
  const len = isConnected.length;
  const find = (index: number): void => {
    for (let i = 0; i < len; i++) {
      if (isConnected[i][index] === 1 && !set.has(i)) {
        set.add(i);
        find(i);
      }
    }
  };
  for (let i = 0; i < len; i++) {
    if (!set.has(i)) {
      ans++;
      find(i);
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-04-30
• 执行用时：92ms
• 内存消耗：40.7MB
• 编程语言：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 findCircleNum(isConnected: number[][]): number {
  const len = isConnected.length;
  const uf = new UnionFind(len);
  for (let i = 0; i < len; i++) {
    const connect = isConnected[i];
    for (let j = 0; j < len; j++) {
      connect[j] === 1 && uf.union(i, j);
    }
  }
  return uf.size;
}

题解 3 - javascript

• 编辑时间：2021-12-04
• 执行用时：36ms
• 内存消耗：6.9MB
• 编程语言：javascript
• 解法介绍：并查集。

typedef struct unionfind
{
    int *father, len, size;
} UnionFind;
UnionFind *unionfind_create(int len)
{
    UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
    uf->size = uf->len = len;
    uf->father = (int *)malloc(sizeof(int) * len);
    for (int i = 0; i < len; i++)
        uf->father[i] = i;
    return uf;
}
void unionfind_free(UnionFind *uf)
{
    free(uf->father);
    free(uf);
}
int unionfind_find(UnionFind *uf, int data)
{
    return uf->father[data] = uf->father[data] == data ? data : unionfind_find(uf, uf->father[data]);
}
void unionfind_union(UnionFind *uf, int data1, int data2)
{
    int p1 = unionfind_find(uf, data1), p2 = unionfind_find(uf, data2);
    if (p1 == p2) return ;
    uf->size--;
    uf->father[p1] = p2;
}
int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
    UnionFind *uf = unionfind_create(isConnectedSize);
    for (int i = 0; i < isConnectedSize; i++) {
        for (int j = 0; j < isConnectedSize; j++) {
            if (isConnected[i][j]) unionfind_union(uf, i, j);
        }
    }
    return uf->size;
}