This repository was archived by the owner on Sep 30, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlab15.cpp
More file actions
89 lines (70 loc) · 1.9 KB
/
lab15.cpp
File metadata and controls
89 lines (70 loc) · 1.9 KB
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
#include "lab.h"
// 按字典顺序排序
bool cmp(std::vector<int>& a, std::vector<int>& b) {
for (int i = 0; i < a.size() && i < b.size(); i++) {
if (a[i] < b[i]) {
return true;
}
else if (a[i] > b[i]) {
return false;
}
}
return a.size() < b.size();
}
/*
* @param graph 图
* @param path 路径
* @param res 结果
* @param p 当前节点
*/
void dfs(std::vector<std::vector<int>>& graph, std::vector<int>& path, std::vector<std::vector<int>>& res, int p) {
int n = graph.size() - 1;
if (p == n) {
res.push_back(path);
return;
}
std::vector<int>& node = graph[p];
for (auto i = node.begin(); i != node.end(); i++) {
path.push_back(*i);
dfs(graph, path, res, *i);
path.pop_back();
}
}
// 输出路径
void output_paths(std::vector<std::vector<int>> res) {
std::sort(res.begin(), res.end(), cmp);
int i = 0;
for (; i < res.size() - 1; i++) {
for (int j = 0; j < res[i].size(); j++) {
std::cout << res[i][j] << " ";
}
std::cout << std::endl;
}
for (int j = 0; j < res[i].size(); j++) {
std::cout << res[i][j] << " ";
}
}
void lab15() {
std::vector<std::vector<int>> graph;
int n, temp;
std::cin >> n;
std::cin.ignore(); // 忽略第一行末尾的换行符
char c;
for (int i = 0; i < n; i++) {
std::vector<int> node;
while (true) {
if ((c = std::cin.get()) == '\n') {
graph.push_back(node);
break;
}
std::cin.putback(c); // 将字符 c 返回输入流
std::cin >> temp;
node.push_back(temp);
}
}
std::vector<std::vector<int>> res;
std::vector<int> path;
path.push_back(0); // 路径从节点 0 开始
dfs(graph, path, res, 0);
output_paths(res);
}