一、题目
给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，如 [0, 1] 表示从 0 到 1 的路径。
每个节点用正整数表示。求这个数据的首节点与尾节点，题目给的用例会是一个首节点，但可能存在多个尾节点。同时图中可能含有环。如果图中含有环，返回 [-1]。
说明：入度为0是首节点，出度为0是尾节点。
二、输入
1
2
3
| 第一行为后续输入的键值对数量N（N ≥ 0）
第二行为2N个数字。每两个为一个起点，一个终点.
|
三、输出
1
| 输出一行头节点和尾节点。如果有多个尾节点，按从小到大的顺序输出
|
备注：
- 如果图有环，输出为 -1
- 所有输入均合法，不会出现不配对的数据
四、示例
1
2
3
4
5
6
| 输入：
4
0 1 0 2 1 2 2 3
输出：
0 3
|
五、题解
- 找有向图的起点和终点。简单来看，入度为 0 的节点是起点，出度为0 的是终点。只要对有向图构造出度和入度表就可以解决
- 考虑到图中有环，就不一定能找到起点或者终点了，根据题意返回-1
- 对应的数据结构上使用入度表和邻接表就可以完成 BFS 遍历无环的节点，也可以找到起点和终点。是否有环逻辑判断也很简单：无环遍历过的节点数是否等于总节点数
5.1 Java 实现
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| package org.stone.study.algo.ex202411;
import java.util.*;
import java.util.stream.Collectors;
public class GraphStartEndPoint {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
scanner.nextLine();
String line = scanner.nextLine();
List<Integer> edgeList = Arrays.stream(line.split(" ")).map(Integer::parseInt).collect(Collectors.toList());
Set<Integer> nodes = new HashSet<>(edgeList);
int n = nodes.size();
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[n];
for(int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for(int i = 0; i < edgeList.size() - 1; i += 2) {
int u = edgeList.get(i);
int v = edgeList.get(i + 1);
graph.get(u).add(v);
inDegree[v]++;
}
List<Integer> ans = findStartAndEnd(graph, inDegree);
System.out.println(ans.stream().map(String::valueOf).collect(Collectors.joining(" ")));
}
private static List<Integer> findStartAndEnd(List<List<Integer>> graph, int[] inDegree) {
List<Integer> ans = new ArrayList<>();
boolean hasCycle = hasCycle(graph, inDegree);
if(hasCycle) {
ans.add(-1);
return ans;
}
int start = -1;
List<Integer> endList = new ArrayList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
start = i;
}
if (graph.get(i).isEmpty()) {
endList.add(i);
}
}
ans.add(start);
ans.addAll(endList);
return ans;
}
private static boolean hasCycle(List<List<Integer>> graph, int[] inDegree) {
List<Integer> visited = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
int[] inDegreeCopy = Arrays.copyOf(inDegree, inDegree.length);
for(int i = 0; i < inDegreeCopy.length; i++) {
if(inDegreeCopy[i] == 0) {
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int u = queue.poll();
visited.add(u);
for(int v : graph.get(u)) {
inDegreeCopy[v]--;
if(inDegreeCopy[v] == 0) {
queue.offer(v);
}
}
}
return visited.size() < inDegreeCopy.length;
}
}
|
5.2 Python实现
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| from collections import deque
def find_start_end_node(adj_list, in_degree):
start = None
def hasCycle(adj_list, in_degree):
nonlocal start
queue = deque()
for i in range(len(in_degree)):
if in_degree[i] == 0:
start = i
queue.append(i)
break
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in adj_list[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count != len(in_degree)
if hasCycle(adj_list, in_degree):
return [-1, -1]
end_list = []
for i in range(len(in_degree)):
if len(adj_list[i]) == 0:
end_list.append(i)
return [start, *end_list]
if __name__ == '__main__':
input()
edge_list = list(map(int, input().split()))
nodes = set(edge_list)
in_degree = [0] * len(nodes)
adj_list = [[] for _ in range(len(nodes))]
for i in range(0, len(edge_list) - 1, 2):
start, end = edge_list[i], edge_list[i + 1]
adj_list[start].append(end)
in_degree[end] += 1
res = find_start_end_node(adj_list, in_degree)
print(' '.join(map(str, res)))
|
