797. All Paths From Source to Target - medium
문제
Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.
The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.
제한사항
- The number of nodes in the graph will be in the range [2, 15].
- You can print different paths in any order, but you should keep the order of nodes inside one path.
입출력 예
1
2
3
4
5
6
7
8
9
10
11
12
Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
| |
v v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
풀이
- Graph, BFS
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
class Solution {
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
int n = graph.size();
int dst = n - 1;
vector<vector<int>> res;
for (auto& index : graph[0]) {
std::queue<std::pair<int, std::vector<int>>> q;
q.push({index, {index}});
// BFS
while(!q.empty()) {
auto item = q.front();
q.pop();
if (item.first == dst) {
item.second.insert(item.second.begin(), 0);
res.push_back(item.second);
}
for (auto& k : graph[item.first]){
std::vector<int> temp(item.second);
temp.push_back(k);
q.push({k, temp});
}
}
}
return res;
}
};