题目描述
为了缓解「力扣嘉年华」期间的人流压力,组委会在活动期间开设了一些交通专线。path[i] = [a, b]
表示有一条从地点 a
通往地点 b
的 单向 交通专线。
若存在一个地点,满足以下要求,我们则称之为 交通枢纽:
- 所有地点(除自身外)均有一条 单向 专线 直接 通往该地点;
- 该地点不存在任何 通往其他地点 的单向专线。
请返回交通专线的 交通枢纽。若不存在,则返回 -1
。
注意:
- 对于任意一个地点,至少被一条专线连通。
样例
输入:path = [[0,1],[0,3],[1,3],[2,0],[2,3]]
输出:3
解释:如下图所示:
地点 0, 1, 2 各有一条通往地点 3 的交通专线,
且地点 3 不存在任何通往其他地点的交通专线。
输入:path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]
输出:-1
解释:如下图所示:不存在满足 交通枢纽 的地点。
限制
1 <= path.length <= 1000
0 <= path[i][0], path[i][1] <= 1000
path[i][0]
与path[i][1]
不相等。
算法
(哈希表) $O(n + m)$
- 使用哈希表记录所有出现节点的编号,并排除拥有出边的节点。
- 使用邻接表记录每个点的所有入边节点(需要去重)。
- 枚举每个没有出边的节点,如果其去重入度的数量等于节点个数减 1,则返回。
时间复杂度
- 每个点和边被遍历一次,故时间复杂度为 $O(n + m)$。
空间复杂度
- 需要 $O(n + m)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int transportationHub(vector<vector<int>>& path) {
unordered_set<int> nodes, out;
unordered_map<int, unordered_set<int>> g;
for (const auto &p : path) {
if (nodes.find(p[0]) == nodes.end())
nodes.insert(p[0]);
if (nodes.find(p[1]) == nodes.end())
nodes.insert(p[1]);
g[p[1]].insert(p[0]);
out.insert(p[0]);
}
for (int k : nodes) {
if (out.find(k) != out.end())
continue;
if (g[k].size() == nodes.size() - 1)
return k;
}
return -1;
}
};