Пошаговый обход графа

Question

Пошаговым обходом графа из вершины v назовём последовательность вершин u1, u2, ..., ur такую, что:

u1 = ur = v,

Каждая вершина графа, достижимая из v, встречается в ней хотя бы один раз,

Между любыми двумя соседними вершинами последовательности в графе существует ребро.

Задан связный неориентированный граф и его вершина v. Выведите любой пошаговый обход этого графа.

Формат ввода

В первой строке входного файла заданы числа N, M и v через пробел — количество вершин и рёбер в графе и начальная вершина обхода (1 <= N <= 100, 0 <= M <= 10000, 1 <= v <= N). Следующие M строк содержат по два числа ui и vi через пробел (1 <= ui, vi <= N); каждая такая строка означает, что в графе существует ребро между вершинами ui и vi.

Формат вывода

В первой строке входного файла выведите число r — количество вершин в найденном пошаговом обходе (; гарантируется, что обход, удовлетворяющий этим ограничениям, существует). Во второй строке выведите сами числа u1, u2, …, ur через пробел.

Пример 1

Ввод

3 2 1
1 2
2 3

Вывод

5
1 2 3 2 1

Пример 2

Ввод

Вывод

5
1 2 3 4 1

Вот мой код:

#include <iostream>
#include <vector>

using namespace std;

int v;

vector<int> way;

void dfs(int start, vector<bool>& visited, vector<vector<int>>& g) {
    visited[start] = true;
    for (int i = 0; i < g[start].size(); i++) {
        int u = g[start][i];
        if (u != 0 && !visited[i]) {
            way.push_back(i + 1);

            if (i == v-1) {
                return;
            }

            dfs(i, visited, g);
        }
    }
}

//главная функция
int main() {
    vector<vector<int>> g;
    int n, m;
    cin >> n >> m >> v;

    g.assign(n, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }

    way.push_back(v);

    vector <bool> visited(n + 1, false);
    //vector <int> prev(n + 1, -1);
    dfs(v-1, visited, g);

    for (int i = 0; i <= n; i++) {visited[i] = false;}

    dfs(way[way.size()-1]-1, visited, g);

    cout << way.size() << "\n";
    for (int i : way) {
        cout << i << " ";
    }
}

Тестирующая система выдала ошибку уже на третьем тесте. Помогите пожалуйста исправить код.

Answer 1

#include <bits/stdc++.h>

using namespace std;

vector<int> used, paths;

vector<vector<int>> graph;
void dfs(int v) {
    used[v] = true;
    paths.push_back(v);
    for (int to : graph[v]) {
        if (!used[to]) {
            dfs(to);
            paths.push_back(v);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

    int n, m, v;
    cin >> n >> m >> v;

    graph = vector<vector<int>>(n + 1);
    used = vector<int>(n + 1, false);

    for (int i = 0; i < m; i++) {
        int f = 0, t = 0;
        cin >> f >> t;
        graph[f].push_back(t);
        graph[t].push_back(f);
    }


    dfs(v);

    cout << paths.size() << '\n';
    for (int v : paths) {
        cout << v << ' ';
    }
    return 0;
}

Вот рабочий код

БЛОГ НА HUSL

Пошаговый обход графа

Ответы (1 шт):