05-图

图也是常用的数据结构之一，关于图有很多经典的算法，最短路径、负权环的判定、关键活动等。

1.可以到达所有点的最少点数目

link:1557. 可以到达所有点的最少点数目 - 力扣（LeetCode）

Description

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1：

img

输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] 输出：[0,3] 解释：从单个节点出发无法到达所有节点。从 0 出发我们可以到达 [0,1,2,5] 。从 3 出发我们可以到达 [3,4,2,5] 。所以我们输出 [0,3] 。 示例 2：

img

输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]] 输出：[0,2,3] 解释：注意到节点 0，3 和 2 无法从其他节点到达，所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。

Solution

本题看似适合使用搜索的方法，例如例1中，4可达节点2和5，然而实际上节点3包含了节点4可以到达的所有节点，因为存在一台边从3到4。实际上，像这样一直向前推导，知道其"入度"为0，那这个入度为0的节点就是我们要找的最少节点集中的一个节点。实际上，所有入度为0的节点都是必要的，这很好理解。而且这些入度为0的节点就可以推导出所有的节点，因为每一个节点要么入度为0，要么可以被前一个节点推导出来，这个所谓的"前一个节点"则或者入度为0，或者能被它的再前一个节点推导出来。

Code

class Solution1 {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        int count = edges.size();
        vector<int> inDegree;
        inDegree.resize(n);
        inDegree = {0};
        for (int i = 0; i < count; i++)
        {
            inDegree[edges[i][1]]=1;
        }
        vector<int> result = {};
        for (int i = 0; i < n; i++)
        {
            if (!inDegree[i]) result.push_back(i);
        }
        return result;
    }
};

2.钥匙和房间

link:841. 钥匙和房间 - 力扣（LeetCode）

Description

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

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

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

示例 1：

输入：rooms = [[1],[2],[3],[]] 输出：true 解释： 我们从 0 号房间开始，拿到钥匙 1。 之后我们去 1 号房间，拿到钥匙 2。 然后我们去 2 号房间，拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间，我们返回 true。 示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]] 输出：false 解释：我们不能进入 2 号房间。

Solution

本题实际上是一道搜索问题，因为求的只是true和false，而不需要求最短的经过房间的数目，所以我们可以使用深度优先搜索也可以使用广度优先搜索。

Code