题目描述
为了缓解「力扣嘉年华」期间的人流压力，组委会在活动期间开设了一些交通专线。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 不存在任何通往其他地点的交通专线。 
示例 2：
输入：path = [[0,3],[1,0],[1,3],[2,0],[3,0],[3,2]]
输出：-1
解释：如下图所示：不存在满足 交通枢纽 的地点。 
提示：
1 <= path.length <= 10000 <= path[i][0], path[i][1] <= 1000path[i][0] 与 path[i][1] 不相等
解法
方法一：统计入度和出度
我们创建两个数组 \(ind\) 和 \(outd\)，分别用于记录每个点的入度和出度，用哈希表 \(s\) 保存每个节点。
接下来，遍历每个节点 \(c\)，如果存在 \(ind[c]\) 等于节点总数减去 \(1\)，并且 \(outd[c]=0\)，说明存在满足条件的交通枢纽，返回 \(c\)。
否则遍历结束，返回 \(-1\)。
时间复杂度 \(O(n + m)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别是节点数量以及路径的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def transportationHub(self, path: List[List[int]]) -> int:
ind = Counter()
outd = Counter()
s = set()
vis = set()
for a, b in path:
if (a, b) in vis:
continue
vis.add((a, b))
s.add(a)
s.add(b)
outd[a] += 1
ind[b] += 1
for c in s:
if ind[c] == len(s) - 1 and outd[c] == 0:
return c
return -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public int transportationHub(int[][] path) {
int[] ind = new int[1001];
int[] outd = new int[1001];
Set<Integer> s = new HashSet<>();
Set<Integer> vis = new HashSet<>();
for (int[] p : path) {
int a = p[0], b = p[1];
if (vis.add(a * 1000 + b)) {
s.add(a);
s.add(b);
ind[b]++;
outd[a]++;
}
}
for (int c : s) {
if (ind[c] == s.size() - 1 && outd[c] == 0) {
return c;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public:
int transportationHub(vector<vector<int>>& path) {
int ind[1001]{};
int outd[1001]{};
unordered_set<int> s;
unordered_set<int> vis;
for (auto& p : path) {
int a = p[0], b = p[1];
if (vis.count(a * 1000 + b)) {
continue;
}
vis.insert(a * 1000 + b);
s.insert(a);
s.insert(b);
ind[b]++;
outd[a]++;
}
for (int c : s) {
if (ind[c] == s.size() - 1 && outd[c] == 0) {
return c;
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func transportationHub(path [][]int) int {
ind := [1001]int{}
outd := [1001]int{}
s := map[int]struct{}{}
vis := map[int]bool{}
for _, p := range path {
a, b := p[0], p[1]
if vis[a*1000+b] {
continue
}
vis[a*1000+b] = true
s[a] = struct{}{}
s[b] = struct{}{}
outd[a]++
ind[b]++
}
for c := range s {
if ind[c] == len(s)-1 && outd[c] == 0 {
return c
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | function transportationHub(path: number[][]): number {
const ind: number[] = new Array(1001).fill(0);
const outd: number[] = new Array(1001).fill(0);
const s: Set<number> = new Set();
const vis: Set<number> = new Set();
for (const [a, b] of path) {
if (vis.has(a * 1000 + b)) {
continue;
}
vis.add(a * 1000 + b);
s.add(a);
s.add(b);
ind[b]++;
outd[a]++;
}
for (const c of s) {
if (ind[c] === s.size - 1 && outd[c] === 0) {
return c;
}
}
return -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
func transportationHub(_ path: [[Int]]) -> Int {
var inDegree = [Int: Int]()
var outDegree = [Int: Int]()
var nodeSet = Set<Int>()
var visitedEdges = Set<String>()
for p in path {
let a = p[0]
let b = p[1]
let edgeKey = "\(a)-\(b)"
if !visitedEdges.contains(edgeKey) {
visitedEdges.insert(edgeKey)
nodeSet.insert(a)
nodeSet.insert(b)
inDegree[b, default: 0] += 1
outDegree[a, default: 0] += 1
}
}
for node in nodeSet {
if inDegree[node, default: 0] == nodeSet.count - 1 && outDegree[node, default: 0] == 0 {
return node
}
}
return -1
}
}
|