Hướng dẫn giải của [CSES 1693] Teleporters Path

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Nhiệm vụ của chúng ta là tìm một đường đi Euler trong một đồ thị có hướng. Có hai điều kiện phải thỏa mãn để đồ thị có đường đi Euler.

Đầu tiên, nếu ta thêm một cạnh mới từ đỉnh ~n~ đến đỉnh ~1~, thì bậc vào và bậc ra của mỗi đỉnh phải bằng nhau.

Thứ hai, tất cả các cạnh phải nằm trong cùng một thành phần liên thông.

Đoạn mã sau sử dụng quay lui để xây dựng một chu trình Euler. Nó đệ quy tạo ra các chu trình bắt đầu và kết thúc tại cùng một đỉnh, và kết hợp các chu trình đó để tạo thành một chu trình Euler. Đoạn mã chạy trong thời gian ~O(n+m)~.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<int> cycle;

void fail() {
    cout << "IMPOSSIBLE\n";
    exit(0);
}

void find_cycle(int node) {
    while (!graph[node].empty()) {
        int next_node = graph[node].back();
        graph[node].pop_back();
        find_cycle(next_node);
    }
    cycle.push_back(node);
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n + 1);
    vector<int> in_degree(n + 1);
    vector<int> out_degree(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        out_degree[a]++;
        in_degree[b]++;
    }

    in_degree[1]++;
    out_degree[n]++;
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] != out_degree[i]) fail();
    }

    find_cycle(1);
    if (cycle.size() != m + 1) fail();

    reverse(cycle.begin(), cycle.end());
    for (auto node : cycle) {
        cout << node << " ";
    }
    cout << "\n";
}

Tài liệu tham khảo

Chương trình tham khảo

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> eu(m), ev(m);
    vector<vector<int>> adj(n + 1);
    vector<int> inDeg(n + 1), outDeg(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        eu[i] = a;
        ev[i] = b;
        adj[a].push_back(i);
        outDeg[a]++;
        inDeg[b]++;
    }

    inDeg[1]++;
    outDeg[n]++;

    for (int i = 1; i <= n; i++) {
        if (inDeg[i] != outDeg[i]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    vector<int> ptr(n + 1, 0);
    vector<char> used(m, 0);
    vector<int> path;

    auto dfs = [&](auto &&self, int v) -> void {
        while (ptr[v] < (int)adj[v].size()) {
            int e = adj[v][ptr[v]++];
            if (used[e])
                continue;
            used[e] = 1;
            self(self, ev[e]);
        }
        path.push_back(v);
    };

    dfs(dfs, 1);
    reverse(path.begin(), path.end());

    if ((int)path.size() != m + 1 || path.front() != 1 || path.back() != n) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    for (int i = 0; i <= m; i++) {
        if (i)
            cout << ' ';
        cout << path[i];
    }
    cout << '\n';
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.