算法(50)-并查集+DFS

算法

 2024/04/28 

整理几道并查集 + DFS 的题目。

[toc]

概念一览

并查集

用途

解决连通性问题。

功能

将两个元素添加到一个集合内
判断两个元素在一个集合

原理

只要用一个一维数组，记录每个元素的父节点，深度遍历，如果根节点相同，就认为是在同一个集合。

因为要根节点相同，所以初始化的时候要指向自己。

优化点

路径压缩

如果节点的跟太深，每次查找遍历次数过多，所以可以在查找的时候，将节点的父节点指向根节点。

按秩合并

秩小的合并到秩大的。

深度优先

和回溯法、递归类似。

广度优先

和迭代类似。

并查集

合作圈

题目

在一个公司里有 N 名员工。这其中有些人有合作关系，有些则没有。他们的合作关系具有传递性。如果已知 A 和 B 有过合作，B 和 C 也有过合作，那么我们可以认为 A 和 C 也有间接的合作关系。所谓的合作圈，就是所有间接或直接合作过的员工集合。你需要输出所有员工中的已知的合作圈总数。

题解

本质是求连通分量的个数。用并查集的结构，遍历所有的合作关系，将有合作关系的员工合并到一个集合内。然后因为只要统计数目，所以用 Set 来存储根节点，最后返回 Set 的长度即可，用不到 DFS。

代码

class DisjointSet {
    constructor(n) {
        this.parent = new Array(n).fill(0).map((_, index) => index);
    }

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

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }
}

function countCooperationCircles(arr) {
    const len = arr.length;
    const ds = new DisjointSet(len);
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (arr[i][j] === 1) {
                ds.union(i, j);
            }
        }
    }
    const uniqueCircles = new Set();
    for (let i = 0; i < len; i++) {
        uniqueCircles.add(ds.find(i));
    }

    return uniqueCircles.size;
}

按公因数计算最大组件大小

题目

给定一个由不同正整数组成的非空数组 nums，考虑下面的构图：

有 nums.length 个节点，按照从 nums[0]到 nums[nums.length-1]标记；

只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j] 之间才有一条边。

返回构图中最大连通组件的大小。

题解

用并查集的思路。首先一个因数 i 是 n 同一组，那么 n / i 也是。遍历每个数的所有因数，创建并查集。再找出联通量最大的那个根节点的数量。

代码

class DisjointSet {
    constructor(n) {
        this.parent = new Array(n).fill(-1).map((_, i) => i);
    }

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

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }
}

function largestComponentSize(nums) {
    const max = Math.max(...nums);
    const ds = new DisjointSet(max + 1);
    for (const num of nums) {
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) {
                ds.union(num, i);
                ds.union(num, Math.floor(num / i));
            }
        }
    }
    const counts = new Array(max + 1).fill(0);
    let ans = 0;
    for (const num of nums) {
        const root = ds.find(num);
        counts[root]++;
        ans = Math.max(ans, counts[root]);
    }
    return ans;
}

DFS

大山的数目

题目

Drizzle 前往山地统计大山的数目，现在收到这片区域的地图，地图中用0（平地）和1（山峰）绘制而成，请你帮忙计算其中的大山数目。

山总是被平地四面包围着，每一座山只能在水平或垂直方向上连接相邻的山峰而形成。一座山峰四面被平地包围，这个山峰也算一个大山。

另外，你可以假设地图的四面都被平地包围着。

题解

这题是求连通分量的个数，用 DFS 来解决。生成一个二维数组来标记每个点是否被访问过。每次遍历所有相连的山峰，同时累加计数。

代码

function countMountains(points) {
    const x = points.length;
    if (x <= 0) {
        return 0;
    }
    const y = points[0].length;
    if (y <= 0) {
        return 0;
    }
    let count = 0;
    const visited = Array.from({ length: x }, () => Array(y).fill(false));

    function dfs(i, j) {
        if (i < 0 || i >= x || j < 0 || j >= y || visited[i][j] || points[i][j] === 0) {
            return;
        }
        visited[i][j] = true;
        dfs(i + 1, j);
        dfs(i, j + 1);
    }

    for (let i = 0; i < x; i++) {
        for (let j = 0; j < y; j++) {
            if (visited[i][j] === false && points[i][j] === 1) {
                count++;
                dfs(i, j);
            }
        }
    }

    return count;
}

跳跃

题目

Drizzle 被困到一条充满数字的方块路中，假设这条路由一个非负的整数数组m组成，Drizzle 最开始的位置在下标 start 处，当他位于下标i位置时可以向前或者向后跳跃m[i]步数，已知元素值为0处的位置是出口，且只能通过出口出去，不可能数组越界，也不能折返，如果跳跃的步数超出数组范围，则也定义为失败，请你通过编程计算出Drizzle能否逃出这里。

题解

把向前向后跳两种选择当做一个长度为2的数组，每个下标对应一个数组，然后用 DFS 来解决。

代码

function jump(arr, start) {
    const len = arr.length;
    const visited = Array.from({ length: len }, () => Array(2).fill(false));
    let res = false;

    function dfs(index) {
        const num = arr[index];

        if (num === 0) {
            res = true;
            return;
        }

        if (index < 0 || index >= len || res) {
            return;
        }

        if (!visited[index][0]) {
            visited[index][0] = true;
            dfs(index + num);
        }

        if (!visited[index][1]) {
            visited[index][1] = true;
            dfs(index - num);
        }
    }

    dfs(start);

    return res;
}

钥匙和房间

题目

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回 false。

题解

用 DFS 来解决。生成一个一维数组来标记每个房间是否被访问过。每次遍历所有房间的钥匙，直到遍历完所有房间。

代码

function canVisitAllRooms(arr) {
    const len = arr.length;
    const visited = new Array(len).fill(false);

    function dfs(index) {
        if (visited[index]) {
            return;
        }

        visited[index] = true;
        for (let i = 0; i < arr[index].length; i++) {
            dfs(arr[index][i]);
        }
    }

    dfs(0);
    const res = visited.filter((v) => v === true);
    return res.length === len;
}

连通网络的操作次数

题目

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。

题解

首先如果线缆的数量比 n - 1 少，那么肯定是没法完全连起来的。然后用 DFS 来解决。用一个 Map 来存放每个节点以及与它相连的边，注意每次一条边对应的两个节点都要操作一遍。最后对所有节点进行遍历，每次遇到没访问过的就是未经连接的网络，需要额外挪动一条线缆。

代码

function makeConnected(n, connections) {
    const len = connections.length;
    if (len < n - 1) {
        return -1;
    }
    const visited = new Array(n).fill(false);
    const edges = new Map();
    let ans = -1;

    for (const [a, b] of connections) {
        if (!edges.has(a)) {
            edges.set(a, []);
        }
        if (!edges.has(b)) {
            edges.set(b, []);
        }
        edges.get(a).push(b);
        edges.get(b).push(a);
    }

    function dfs(u) {
        visited[u] = true;
        if (edges.get(u)) {
            for (const v of edges.get(u)) {
                if (!visited[v]) {
                    dfs(v);
                }
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            ans++;
        }
    }
    return ans;
}