Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- class Graph {
- private:
- vector<vector<int> > adj;
- vector<bool> used;
- vector<int> prev;
- public:
- Graph(int vertex_count) {
- adj.resize(vertex_count);
- used.resize(vertex_count, false);
- prev.resize(vertex_count, -1);
- }
- void add_edge(int from, int to) {
- adj[from].push_back(to);
- adj[to].push_back(from); // Граф неориентированный
- }
- bool BFS(int start_v, int end_v) {
- queue<int> q;
- q.push(start_v);
- used[start_v] = true;
- while (!q.empty()) {
- int cur_v = q.front();
- q.pop();
- if (cur_v == end_v) {
- return true;
- }
- for (size_t i = 0; i < adj[cur_v].size(); ++i) {
- int nei = adj[cur_v][i];
- if (!used[nei]) {
- q.push(nei);
- used[nei] = true;
- prev[nei] = cur_v; // Запоминаем предыдущую вершину
- }
- }
- }
- return false;
- }
- vector<int> get_path(int start_v, int end_v) {
- vector<int> path;
- int v = end_v;
- while (v != -1) {
- path.push_back(v);
- v = prev[v];
- }
- // Разворачиваем путь вручную
- vector<int> reversed_path;
- for (int i = path.size() - 1; i >= 0; --i) {
- reversed_path.push_back(path[i]);
- }
- return reversed_path;
- }
- };
- int main() {
- int n, m;
- cin >> n >> m;
- int a, b;
- cin >> a >> b;
- a--;
- b--;
- Graph graph(n);
- for (int i = 0; i < m; ++i) {
- int u, v;
- cin >> u >> v;
- u--;
- v--;
- graph.add_edge(u, v);
- }
- bool path_exists = graph.BFS(a, b);
- if (!path_exists) {
- cout << -1 << endl;
- } else {
- vector<int> path = graph.get_path(a, b);
- cout << path.size() - 1 << endl;
- for (size_t i = 0; i < path.size(); ++i) {
- cout << path[i] + 1;
- if (i + 1 < path.size()) {
- cout << " ";
- }
- }
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
