交通枢纽

标签: 图

难度: Medium

为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。`path[i] = [a, b]` 表示有一条从地点 `a`通往地点 `b` 的 **单向** 交通专线。 若存在一个地点，满足以下要求，我们则称之为 **交通枢纽**： - 所有地点（除自身外）均有一条 **单向** 专线 **直接** 通往该地点； - 该地点不存在任何 **通往其他地点** 的单向专线。 请返回交通专线的 **交通枢纽**。若不存在，则返回 `-1`。 **注意：** - 对于任意一个地点，至少被一条专线连通。 **示例 1：** >输入：`path = [[0,1],[0,3],[1,3],[2,0],[2,3]]` > >输出：`3` > >解释：如下图所示： > 地点 `0,1,2` 各有一条通往地点 `3` 的交通专线， > 且地点 `3` 不存在任何**通往其他地点**的交通专线。 >![image.png](https://pic.leetcode-cn.com/1663902572-yOlUCr-image.png){:width=200px} **示例 2：** >输入：`path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]` > >输出：`-1` > >解释：如下图所示：不存在满足 **交通枢纽** 的地点。 >![image.png](https://pic.leetcode-cn.com/1663902595-McsEkY-image.png){:width=200px} **提示：** - `1 <= path.length <= 1000` - `0 <= path[i][0], path[i][1] <= 1000` - `path[i][0]` 与 `path[i][1]` 不相等

Submission

运行时间: 31 ms

内存: 16.4 MB

class Solution:
    def transportationHub(self, path: List[List[int]]) -> int:
        res = set()
        res1 = defaultdict(int)
        res2 = defaultdict(int)

        for i, j in path:
            res.add(i)
            res.add(j)
            res1[i] += 1
            res2[j] += 1
        n = len(res)
        for c in res:
            if res1[c] == 0 and res2[c] == n - 1:
                return c
        return -1

Explain

题解的思路是首先使用两个字典来记录每个节点的出度和入度。res1字典记录节点的出度（即从该节点出发的边数），res2字典记录节点的入度（即指向该节点的边数）。同时，使用一个集合res来记录所有出现过的节点。遍历一遍输入的边列表，填充这两个字典和节点集合。接着，遍历集合中的每个节点，检查是否存在一个节点c，使得该节点的出度为0（res1[c] == 0）且入度为其他所有节点到它的总数（res2[c] == n - 1，其中n是所有不同节点的数量）。如果找到这样的节点，就返回该节点，否则返回-1。这种方法直接通过统计入度和出度来判断是否满足题目中的交通枢纽条件。

时间复杂度: O(m+n)

空间复杂度: O(n)

class Solution:
    def transportationHub(self, path: List[List[int]]) -> int:
        res = set() # 存储所有出现过的节点
        res1 = defaultdict(int) # 记录每个节点的出度
        res2 = defaultdict(int) # 记录每个节点的入度

        for i, j in path:
            res.add(i) # 将起点添加到节点集合中
            res.add(j) # 将终点也添加到节点集合中
            res1[i] += 1 # 增加从i出发的边数
            res2[j] += 1 # 增加指向j的边数
        n = len(res) # 计算总节点数
        for c in res:
            if res1[c] == 0 and res2[c] == n - 1: # 检查节点c是否没有出度且入度完全来自其他所有节点
                return c
        return -1 # 如果没有找到符合条件的节点，返回-1

Explore

在题解中使用两个字典来分别记录出度和入度，主要是为了清晰地区分这两种不同类型的信息。出度表示从某个节点出发到其他节点的边的数量，而入度表示指向某个节点的边的数量。这种分开记录的方式使得在后续的逻辑判断中，可以更直接地访问到每种类型的数据，从而简化对节点是否是交通枢纽的判断。如果使用一个字典同时记录出度和入度，则需要在每个记录中同时维护两个数值，这可能会使数据结构处理起来更复杂，且在实际编码时可能增加错误发生的概率。

在题解中计算节点总数n时，并没有直接考虑可能存在的孤立节点。这是因为题解假定所有节点至少作为起点或终点出现在给定的path列表中。如果存在孤立节点，即那些未在任何边中出现的节点，它们不会被添加到节点集合res中，因此不会被计入总节点数n。这种处理方式可能会影响到交通枢纽的判断，尤其是在需要准确判断每个节点的入度和出度是否符合条件的场景下。

题解中的方法主要关注于节点的出度和入度的特定条件，即出度为0且入度等于其他所有节点的总数（n-1）。这种方法实际上并没有直接考虑图中可能存在的环路对结果的影响。在有环路的情况下，环路中的节点可能会影响到其他节点的入度计数，但只要这些节点不满足出度为0的条件，它们就不会被误判为交通枢纽。因此，只要环路不直接影响到候选节点c的出度和入度符合上述条件，该方法仍然有效。